## Friday, 21 February 2014

### Counting Sort in java

#### Background

Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence.

#### Code :

```import java.util.Arrays;

/**
* Created with IntelliJ IDEA.
* User: aniket
* Date: 19/2/14
* Time: 8:03 PM
*/
public class CountingSort {

public int[] sort(int[] array) {

int maxValue = getMaxValue(array);
return countingSort(array,maxValue);

}

public int[] countingSort(int[] input, int maxValue){

int[] countArray = new int[maxValue+1];
for(int no : input){
countArray[no] = countArray[no] + 1;
}

for(int i=1;i<countArray.length;i++){
countArray[i] = countArray[i] + countArray[i-1];
}

int[] output = new int[input.length];

for(int i=output.length-1;i>=0;i--){

output[countArray[input[i]]-1] = input[i];
countArray[input[i]] = countArray[input[i]] -1;

}

return output;

}

private int getMaxValue(int[] array){

int maxValue = Integer.MIN_VALUE;
for(int no : array){
if(no > maxValue){
maxValue = no;
}
}
return maxValue;
}

public static void main(String args[]){

int[] array = new int[]{2,7,5,9,4,7,1,0};
System.out.println("Array Before Sort : " + Arrays.toString(array));
System.out.println("Array after Sort : " + Arrays.toString(new CountingSort().sort(array)));

}

}
```

#### Output :

Array Before Sort : [2, 7, 5, 9, 4, 7, 1, 0]
Array after Sort : [0, 1, 2, 4, 5, 7, 7, 9]

NOTE : The modified count array indicates the position of each object in the output sequence.

#### Time Complexity

Time Complexity: O(n+k) where n is the number of elements in input array and k is the range of input.
Auxiliary Space:
O(n+k)