Home Arrays Counting Sort

Counting Sort

by nikoo28
0 comment

Counting sort is not a comparison sort algorithm and gives O(n) complexity for sorting. To achieve O(n) complexity, counting sort assumes that each of the elements is an integer in the range of 1 to K, for some integer K. When K = O(n), the counting sort works in O(n) time. The basic idea of counting sort is to determine, for each input elements X, the number of elements less than X. This information can be used to place directly into its correct position. For example, if there are 10 elements less than X, then X belongs to position 11 in the output.

In the below example, arr[0..n – 1] is the input array with length n. In counting sort we need two more arrays: let us assume array temp[0..n – 1] as another array and out[0..n – 1] as the final sorted array.

Here is an implementation of the algorithm:-

void countingSort(int arr[], int size, int out[], int k)
{
	//arr[] - is the original array.
	//size - the size of array
	//out[] - the final sorted array
	//K - the maximum value in array
	
	int temp[k], i ,j;  // thus space complexity = O(K)
	
	for(i = 0;i < k;i++)
		temp[i] = 0;    // initialize all to ZERO
		
	//now we traverse through the original array
	//and increment the count at the location.
	//Eg: if we get an element "56", then we do temp[56]++
	for(j = 0;j < size;j++)
		temp[arr[j]] = temp[arr[j]] + 1;
	
	// temp[i] now contains the number of elements equal to i
	
	for(i = 1;i < K;i++)
		temp[i] = temp[i] + temp[i-1];
		
	// temp[i] now contains the number of elements <= i
	
	//time to make the final sorted array
	for(j = size;j >= 0;j--)
	{
		//filling the array
		out[temp[arr[j]]] = arr[j];
		
		//decrement the count for each added element.
		temp[arr[j]] = temp[arr[j]] - 1;
	}
}
0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More