This sorting algorithm takes advantage of the range of the numbers in the array to be sorted.
Say the range is 0..k then it can sort the array in O(k). If k is less than or equal to n, we are in great advantage because we can sort this array in linear time i.e. O(n).
Following is my implementation:
void countSort(int *a, int size)
{
int max = Max(a);
int *c = new int[max+1];
int *sorted = new int[size];
for( int i=0; i<size; ++c[a[i++]] ); // Step 1
for( i=1; i<max; c[i++] += c[i1] ); // Step 2:Get the number of elements less than each number
for(i=size1; i >= 0; i) // Step 3
{
sorted[c[a[i]]1] = a[i];
c[a[i]];
}
for(i=0; i<size; ++i)
a[i] = sorted[i];
}
Example 
Input Array
Step 1: Array C
Step 2: Array C
Say the range is 0..k then it can sort the array in O(k). If k is less than or equal to n, we are in great advantage because we can sort this array in linear time i.e. O(n).
The algorithm first determine for each element x the number of elements less than x. One of the advantage of this algorithm is its stability.
Following is my implementation:
void countSort(int *a, int size)
{
int max = Max(a);
int *c = new int[max+1];
int *sorted = new int[size];
for( int i=0; i<size; ++c[a[i++]] ); // Step 1
for( i=1; i<max; c[i++] += c[i1] ); // Step 2:Get the number of elements less than each number
for(i=size1; i >= 0; i) // Step 3
{
sorted[c[a[i]]1] = a[i];
c[a[i]];
}
for(i=0; i<size; ++i)
a[i] = sorted[i];
}
Example 
Input Array
2  5  3  0  2  3  0  3 
Step 1: Array C
2  0  2  3  0  1 
Step 2: Array C
2

2

4

7

7

8

Step 3:
a[7] = 3 c[3] = 7 sorted [6] = 3 => c[3] = 6
3  
a[6] = 0 c[0] = 2 sorted[1] = 0 => c[0] = 1
0  3  
a[5] = 3 c[3] = 6 sorted[5] = 3 => c[3] = 5
0  3  3  
.
.
.
.
In the End Sorted array
0  0  2  2  3  3  3  5 
No comments:
Post a Comment