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.
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)
Auxiliary Space: O(n+k)
No comments:
Post a Comment