Technical Interview Questions: Counting sort

Counting sort will sort the elements of the array on the basis of its array position. It will set the value of array position to 1 and 0 if the element is present or not.

For example if element 10 is present then this sort method will set a[10] to 1. By default a[10] will be set to 0. Then the array a is read one by one. If a[i] is set to 1, then the value will be outputted to entered into a final array. So the output/final array will contain sorted elements.

Algorithm:

Initialize i to 0
Set count[a[i]] to 1(Set the value at location a[i] to 1).
Repeat step 2 till i reaches n-1.
Initialize i to 0 again
If count[i] is not 0 then initialize j to 0 and output count[i].
Repeat step 5 till j < length of(count[i])
Repeat steps 5 and 6 till i reaches count.length.

Raw Iterations:

For example if the input array is 10, 30, 20, 30.
Then this algorithm will set a[10] to 1, a[20] to 1 and a[30] to 2.
Then it will iterate a from i = 0 to 30 and will output 10, 20, 20, 30

 
public static int a[] = {1,2,8,5,3,6,4,10};
public static int count[] = new int[100];

for(int i=0; i < a.length; i++) 
{
 count[a[i]]++;
}

int k = 0;
for(int i=0; i < count.length; i++) 
{
 if(count[i] != 0)
 {
  for(int j=0;j < count[i]; j++) 
  {
   a[k++] = i;
  }
 }
}

Complexity:

Time complexity is O(n) since we iterate through the input array twice.
Space complexity is O(n) since we need additional space to store the number of times the element is repeated.