Count sort java program


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

Popular posts from this blog

SQL basic interview question

gsutil Vs Storage Transfer Service Vs Transfer Appliance