vibudh is talking

Posts tagged ‘java’

Counting Sort – An optimised technique

In Computer Science, counting sort is a way of sorting of a collection of numbers found in a predefined range. This property is used in Counting Sort technique to make the running time linear in the number of items and the maximum key values. So it is very useful in situations where the number of items are significantly larger than the range. Counting Sort in used mostly as a subroutine in Radix Sort, which makes the sorting technique efficient even with larger values of the range.

A basic algorithm of the Counting Sort is given below that is used and discussed in most places:

/*array[] is the original array with length array.lenght
f[]  and cf[] are the frequency and cumulative frequency with length r(length of the range)
s[] is the sorted array
*/

for( int i = 0; i < array.length; i++)
f[array[i]]++;                                        //Calculating the Frequency for each element

cf[0] = f[0];                                            //Calculating the Cumulative Frequency for each element
for(int i = 1; i < r-1; i++)
cf[i] = f[i] + cf[i-1];

for( int i = n-1; i >= 0; i–)
{ s[cf[a[i]]] = a[i];
cf[a[i]]–;
}

 

We can see that in the algorithm discussed worldwide there is use of 2 extra arrays for calculating the frequency and cumulative frequency for the elements. Now there is a simpler method for the Counting Sort that we are going to discuss below:

/*array[] is the original array with length array.lenght
f[] is the frequency with length r(length of the range)
s[] is the sorted array
*/

for( int i = 0; i < array.length; i++)
f[array[i]]++;                                        //Calculating the Frequency for each element

int count =0;                                        //variable for the value of sorted elements
for( int i = 0; i<r; i++)                      //putting the value one by one
while ( f[i] > 0 )
{s[count] = i;
f[i]–;
count++;
}

I consider this algorithm better for Counting sort method as it is a simpler method with lesser steps and does not uses an extra array for storing the cumulative frequency of the array.