class CountSort {
public static void sort(int[] array) {
// Find largest element
int max = Integer.MIN_VALUE;
for(int element : array) {
if(less(max, element)) {
max = element;
}
}
// Create an array with largest element
int[] frequency = new int[max+1];
// count all element occurances in frequency array
for(int element : array) {
frequency[element]++;
}
int j = 0;
// Iterate frequency array from left to right and copy into array
for(int i = 0; i < frequency.length; i++) {
// if frequency[i] > 0 then element exist in array so copy back in the order
while(frequency[i] > 0) {
array[j++] = i;
frequency[i]--;
}
}
}
private static boolean less(int key1, int key2) {
return key1 < key2;
}
private static void display(int[] array) {
for(int key : array) {
System.out.print(key + " ");
}
}
public static void main (String[] args) {
int[] array = new int[] {11,13,13,13,7,12,16,9,6,6,6,15,2,4,6};
System.out.println("Unsorted array : ");
display(array);
sort(array);
System.out.println("\nSorted array : ");
display(array);
}
}
Unsorted array :
11 13 13 13 7 12 16 9 6 6 6 15 2 4 6
Sorted array :
2 4 6 6 6 6 7 9 11 12 13 13 13 15 16
Comments
Post a Comment