Quick sort program | Improvement | Use Insertion sort for small sub array


class QuickSort {
    // CUTOFF to use insertion sort intead of quick sort for sub array 
    private static final int CUTOFF = 5;
    
    public static void sort(int[] array) {
        sort(array, 0, array.length-1);
    }
    
    private static void sort(int[] array, int low, int high) {
        // -1 to allow fist pass to use quick sort
        if(high <= low + CUTOFF - 1) { // improvement : use insertion sort for small sub array
            InsertionSort.sort(array, low, high);
            return;
        }
        int j = partition(array, low, high);
        sort(array, low, j-1);
        sort(array, j+1, high);
    }
    
    private static int partition(int[] array, int low, int high) {
        int i = low;
        int j = high+1;
        // find item on left to swap
        while(true) {
            while(less(array[++i], array[low])) {
                if(i == high) { // corner case : avoid ArrayIndexOutOfBoundsException
                    break;
                }
            }
            
            // find item on right to swap
            while(less(array[low], array[--j])) {
                if(j == low) { // corner case : avoid ArrayIndexOutOfBoundsException
                    break;
                }
            }
            
            // check if pointers cross
            if(i >= j) { 
                break;
            }
            
            // swap array[i] with array[j]
            swap(array, i, j);
        }
        // swap array[low] with array[j]
        swap(array, low, j);
        
        // all elements before jth index are less then jth element 
        // and all elements after jth elements are greater than jth element 
        // so jth element is the partition elemrnt. Return index j 
        return j;
    }
    
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    
    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) {
	    // Test average case 
		int[] array = new int[] {11,13,7,12,16,9,24,5,10,3};
		System.out.println("Unsorted array : ");
		display(array);
		
		sort(array);
		System.out.println("\nSorted array : ");
		display(array);
	}
	
    private static class InsertionSort {
        static void sort(int[] array, int low, int high) {
            for(int i = low+1; i <= high; i++) {
                for(int j = i; j > 0 && less(array[j], array[j-1]); j--) {
                    swap(array, j, j-1);
                }
            }
        }
    }
}

Output
Unsorted array : 
11 13 7 12 16 9 24 5 10 3 
Sorted array : 
3 5 7 9 10 11 12 13 16 24 

Comments

Popular posts from this blog

SQL basic interview question

gsutil Vs Storage Transfer Service Vs Transfer Appliance