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
Post a Comment