It’s a linear time sorting algorithm which is different from the comparison based sorting algorithms like quick sort or heap sort. Counting sort is also a linear time sorting algorithm which is explained in my previous post.
Let us understand this algorithm using an example.
Consider the array [235, 10, 784, 69, 51]
We first sort the numbers based on the least significant digit, i.e the digit at 1’s place. It becomes [10, 51, 784, 235, 69]. Observe that the these numbers are now sorted according to it’s last digit ([0,1,4,5,9]).
Next we consider the digits at 10’s place and sort them. It transforms to
[10, 235, 51, 69, 784]. These are sorted according to the last but one digits ([1,3,5,6,8])
Similarly in the next step it becomes [10, 51, 69, 235, 784].
Now the entire array is sorted! We no longer need to sort array because we have at most 3 digits in any number.
Implementation details:
Suppose there are at most D digits in any number, we call the counting sort D times for each place.
Let us briefly know how counting sort works. For more details, you can check my previous post.
It first groups the numbers into buckets. The result of this is a count array of size 10 (assuming the numbers are in the range 0-9).
Calculate the prefix array of this, we get the sorted positions of given numbers.
Then we use a temporary array to arrange the numbers in sorted order.
An alternative implementation could be to maintain a list of numbers for each bucket, and merging them to a sorted array. But this approach takes extra memory for the list of buckets.
The following code shows the implementation of the above algorithm.
| #include <iostream> | |
| #include <list> | |
| #include <vector> | |
| using namespace std; | |
| //Returns the digit at a particular place in given number | |
| int get_digit(int num, int place) | |
| { | |
| return (num/place)%10; | |
| } | |
| //Sort the numbers based on the place value | |
| //It returns false if no number has a digit in the given place | |
| bool counting_sort(vector<int>& nums, int place) | |
| { | |
| vector<int> count(10); | |
| bool more_digits = false; | |
| int i; | |
| //Divide the numbers into buckets using the place value | |
| for( i = 0; i < nums.size(); i++ ) | |
| { | |
| if( nums[i]/place > 0 ) | |
| more_digits = true; | |
| count[get_digit(nums[i],place)]++; | |
| } | |
| if( more_digits ) | |
| { | |
| //Calculate prefix array to find the actual indices in sorted array | |
| for( i = 1; i < 10; i++ ) | |
| { | |
| count[i] += count[i-1]; | |
| } | |
| //Use a temp array to store the sorted list | |
| vector<int> temp(nums.size()); | |
| for( i = nums.size()-1; i >= 0; i-- ) | |
| { | |
| int ind = get_digit(nums[i],place); | |
| if( count[ind] > 0 ) | |
| { | |
| temp[count[ind]-1] = nums[i]; | |
| count[ind]--; | |
| } | |
| } | |
| nums = temp; //Change the original array | |
| } | |
| return more_digits; | |
| } | |
| void radix_sort(vector<int>& nums) | |
| { | |
| //Edge case | |
| if( nums.size() < 2 ) | |
| return; | |
| int place = 1; | |
| //For each place, sort numbers using counting sort | |
| //stop when there are no more digits at given place | |
| while( counting_sort(nums, place) ) | |
| place *= 10; | |
| } | |
| //This implementation uses O(n) extra memory | |
| void radix_sort1(vector<int>& nums) | |
| { | |
| int i; | |
| int f = 1; | |
| while(true) | |
| { | |
| bool digits_left = false; | |
| vector<list<int>> buckets(10); | |
| for(i = 0; i < nums.size(); i++) | |
| { | |
| int temp = nums[i]/f; | |
| if( temp != 0) | |
| digits_left = true; | |
| buckets[temp%10].push_back(nums[i]); | |
| } | |
| vector<int> helper(nums.size()); | |
| int ind = 0; | |
| for(i = 0; i < 10; i++) | |
| { | |
| list<int>::iterator it; | |
| for(it = buckets[i].begin(); it != buckets[i].end(); ++it) | |
| helper[ind++] = *it; | |
| } | |
| nums = helper; | |
| if(!digits_left) | |
| break; | |
| f *= 10; | |
| } | |
| } | |
| int main() | |
| { | |
| int n; | |
| cin >> n; | |
| vector<int> nums(n); | |
| int i; | |
| for(i = 0; i < n; i++) | |
| { | |
| cin >> nums[i]; | |
| } | |
| radix_sort(nums); | |
| for(i = 0; i < n; i++) | |
| cout << nums[i] << " "; | |
| return 0; | |
| } |
by