trypots.nethomeQuickSort
QuickSort is a popular sorting algorithm that is used in practice for many library sorts. It has good performance, sorts in place, and makes efficient use of modern processors. It is a divide-and-conquer algorithm that recursively sorts subarrays with an array until the entire array is sorted. The key to quicksort is the partitioning algorithm. When partitioning is complete, the array is divided into two halves with a pivot element dividing the two halves. Elements to the left of the pivot are less than the pivot, and elements to the right of the pivot are greater than the pivot. The pivot itself is also therefore in place with regards to the final sort. Recursive calls to partition continue sorting subarrays in the same way.
To implement partition(), we choose arbitrarily an element to serve as the pivot. This implementation uses the first element as the pivot element. Although of course it will end up in place dividing the two halves, the algorithm first scans through the rest of the array in order to get the other elements in place. The pivot remains in place and is a constant value used for each comparison. We scan the array from left to right until we find an element greater than the pivot, and scan from right to left until we find an element less than the pivot. These can be exchanged, since they are in the wrong place with respect to the pivot. When the scanning indices, i and j, cross over each other then the scanning is complete: all elements on the left are less than the pivot and all elements on the right are greater than the pivot. The pivot can now be exchanged with j, the first element in the right half. Everything to the left is greater than the pivot, and everything to the right is less than the pivot. The function returns j, which is the location of the pivot as the result of partitioning. The next recursive calls to quicksort will sort the subarrays to the left and right of the pivot, and the process continues until the entire array is sorted.
A worst case scenario for quicksort is when there are many duplicate values. See Robert Sedgewick and Kevin Wayne's book Algorithms for a solution to this problem using three-way partitioning to make the sort more efficient in this common real-world situation, as well as further valuable discussion of quicksort.
Since quicksort peforms so well, is there a reason to prefer it to another good sorting algorithm such as mergesort? Yes, compared to quicksort, mergesort is stable. Also, in some cases mergesort can perform poorly, although this can be alleviated with more sophisticated versions of the algorithm (again, see discussion in Sedgewick and Wayne's textbook Algorithms for more information).
QuickSort:
public class QuickSort {
public static void sort(int[] a) {
sort(a, 0, a.length - 1);
}
private static void sort(int[] a, int lo, int hi) {
// Because scanning right to left will end at the beginning of the (sub)array,
// this case will signal the end of recursive calls.
if(hi <= lo) return;
//Go quicksort
int j = partition(a, lo, hi);
sort(a, lo, j-1);
sort(a, j+1, hi);
}
private static int partition(int[] a, int lo, int hi) {
int i = lo;
int j = hi + 1;
int pivotval = a[lo];
int temp ;
while(true) {
//increment i until an element greater than pivotval is encountered.
do {
i++;
if (i == hi) {
break;
}
} while(a[i] < pivotval);
//decrement j until an element less than pivotval is encountered.
do {
j--;
if(j == lo) {
break;
}
} while(a[j] >= pivotval);
//check if indices have crossed
if(i >= j)
break;
//exchange elements and continue checking
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
//finish partitioning by placing pivot value in its correctly sorted place. In the trivial
// case of an already sorted array, it exchanges the pivot with itself.
a[lo] = a[j];
a[j] = pivotval;
return j;
}
//compiling and running QuickSort.java will execute this test code in main()
public static void main(String[] args) {
int[] a = {7,8,12,18,32,6,17,21,13,9,5,8,25,20,16,12,3};
sort(a);
if(isSorted(a)) {
System.out.println("sort succeeded.");
}
else {
System.out.println("sort failed.");
}
}
//helper function to test for correctness
private static boolean isSorted(int[] a) {
for(int i = 1; i < a.length; i++) {
if(a[i] < a[i-1]) {
return false;
}
}
return true;
}
}