Basics
The basic version of Quicksort is pretty simple and can be implemented just in few lines of code:
public static void basicQuickSort(long arr[], int beginIdx, int len) { if ( len <= 1 ) return; final int endIdx = beginIdx+len-1; // Pivot selection final int pivotPos = beginIdx+len/2; final long pivot = arr[pivotPos]; Utils.swap(arr, pivotPos, endIdx); // partitioning int p = beginIdx; for(int i = beginIdx; i != endIdx; ++i) { if ( arr[i] <= pivot ) { Utils.swap(arr, i, p++); } } Utils.swap(arr, p, endIdx); // recursive call basicQuickSort(arr, beginIdx, p-beginIdx); basicQuickSort(arr, p+1, endIdx-p); }
The code looks pretty simple and easily readable. Pivot selection is trivial and doesn’t require any explanation. The partitioning process can be illustrated using following figure:
public static void basicQuickSort(long arr[], int beginIdx, int len) { if ( len <= 1 ) return; final int endIdx = beginIdx + len - 1; final int pivotIdx = getPivotIdx(arr, beginIdx, len); final long pivot = arr[pivotIdx]; Utils.swap(arr, pivotIdx, endIdx); int p = partition(arr, beginIdx, len, pivot); Utils.swap(arr, p, endIdx); basicQuickSort(arr, beginIdx, p-beginIdx); basicQuickSort(arr, p+1, endIdx-p); } public static int partition(long[] arr, int beginIdx, int len, long pivot) { final int endIdx = beginIdx + len - 1; int p = beginIdx; for(int i = beginIdx; i != endIdx; ++i) { if ( arr[i] <= pivot ) { Utils.swap(arr, i, p++); } } return p; } public static int getPivotIdx(long arr[], int beginIdx, int len) { return beginIdx+len/2; }
Now let’s have a look how it performs vs Java 1.6 sort algorithm. For the test I will generate array using following loop:
static Random rnd = new Random(); private static long[] generateData() { long arr[] = new long[5000000]; for(int i = 0; i != arr.length; ++i) { arr[i] = rnd.nextInt(arr.length); } return arr; }
Then I run each JDK 6 Arrays.sort() and basicQuickSort() for 30 times and took the average run time as the result. New set of random data was generated for each run. The result if that exercise is this:
arr[i]=rnd.nextInt(arr.length) | |
Java 6 Arrays.sort | 1654ms |
basicQuickSort | 1431ms |
Not that bad. Now look what would happen if input data has some more repeated elements. To generated that data, I just divided nextInt() argument by 100:
arr[i]=rnd.nextInt(arr.length) | arr[i]=rnd.nextInt(arr.length/100) | |
Java 6 Arrays.sort | 1654ms | 935ms |
basicQuickSort | 1431ms | 2570ms |
public static int getPivotIdx(long arr[], int beginIdx, int len) { if ( len <= 512 ) { int p1 = beginIdx; int p2 = beginIdx+(len>>>1); int p3 = beginIdx+len-1; if ( arr[p1] > arr[p2] ) { int tmp = p1; p1 = p2; p2 = tmp; } if ( arr[p2] > arr[p3] ) { p2 = p3; } if ( arr[p1] > arr[p2] ) { p2 = p1; } return p2; } else { int p1 = beginIdx+(len/4); int p2 = beginIdx+(len>>1); int p3 = beginIdx+(len-len/4); int p4 = beginIdx; int p5 = beginIdx+len-1; if ( arr[p1] > arr[p2] ) { int tmp = p1; p1 = p2; p2 = tmp; } if ( arr[p2] > arr[p3] ) { int tmp = p2; p2 = p3; p3 = tmp; } if ( arr[p1] > arr[p2] ) { int tmp = p1; p1 = p2; p2 = tmp; } if ( arr[p3] > arr[p4] ) { int tmp = p3; p3 = p4; p4 = tmp; } if ( arr[p2] > arr[p3] ) { int tmp = p2; p2 = p3; p3 = tmp; } if ( arr[p1] > arr[p2] ) { p2 = p1; } if ( arr[p4] > arr[p5] ) { p4 = p5; } if ( arr[p3] > arr[p4] ) { p3 = p4; } if ( arr[p2] > arr[p3] ) { p3 = p2; } return p3; } }
Here are results after improvements in pivot selection strategy:
arr[i]=rnd.nextInt(arr.length) | arr[i]=rnd.nextInt(arr.length/100) | |
Java 6 Arrays.sort | 1654ms | 935ms |
basicQuickSort | 1431ms | 2570ms |
basicQuickSort with ‘better’ pivot | 1365ms | 2482ms |
After implementation of such algorithm partitioning function is getting much more complicated. In that implementation the result of the partitioning is lengths of two bound partitions:
public static long partition(long[] arr, int beginIdx, int endIdx, long pivot) { int i = beginIdx-1; int l = i; int j = endIdx+1; int r = j; while ( true ) { while(arr[++i] <> pivot){} if ( i >= j ) break; Utils.swap(arr, i, j); if ( arr[i] == pivot ) { Utils.swap(arr, i, ++l); } if ( arr[j] == pivot ) { Utils.swap(arr, j, --r); } } // if i == j then arr[i] == arr[j] == pivot if ( i == j ) { ++i; --j; } final int lLen = j-l; final int rLen = r-i; final int pLen = l-beginIdx; final int exchp = pLen > lLen ? lLen: pLen; int pidx = beginIdx; for(int s = 0; s <= exchp; ++s) { Utils.swap(arr, pidx++, j--); } final int qLen = endIdx-r; final int exchq = rLen > qLen ? qLen : rLen; int qidx = endIdx; for(int s = 0; s <= exchq; ++s) { Utils.swap(arr, qidx--, i++); } return (((long)lLen)<<32)|rlen; }
The pivot selection has to be changed as well, but more just for convenience, the idea remains absolutely the same. Now it returns actual value of pivot, instead of index:
public static long getPivot(long arr[], int beginIdx, int len) { if ( len <= 512 ) { long p1 = arr[beginIdx]; long p2 = arr[beginIdx+(len>>1)]; long p3 = arr[beginIdx+len-1]; return getMedian(p1, p2, p3); } else { long p1 = arr[beginIdx+(len/4)]; long p2 = arr[beginIdx+(len>>1)]; long p3 = arr[beginIdx+(len-len/4)]; long p4 = arr[beginIdx]; long p5 = arr[beginIdx+len-1]; return getMedian(p1, p2, p3, p4, p5); } }
And here is the main method, which is slightly changed as well:
public static void threeWayQuickSort(long[] arr, int beginIdx, int len) { if ( len < 2 ) return; final int endIdx = beginIdx+len-1; final long pivot = getPivot(arr, beginIdx, len); final long lengths = threeWayPartitioning(arr, beginIdx, endIdx, pivot); final int lLen = (int)(lengths>>32); final int rLen = (int)lengths; threeWayQuickSort(arr, beginIdx, lLen); threeWayQuickSort(arr, endIdx-rLen+1, rLen); }
now let’s compare it with Java 6 sort:
arr[i]=rnd.nextInt(arr.length) | arr[i]=rnd.nextInt(arr.length/100) | |
Java 6 Arrays.sort | 1654ms | 935ms |
basicQuickSort | 1431ms | 2570ms |
basicQuickSort with ‘better’ pivot | 1365ms | 2482ms |
Three-way partitioning Quicksort | 1330ms | 829ms |
public static void threeWayQuickSort(long[] arr, int beginIdx, int len) { if ( len < 2 ) return; if ( len < 17 ) { InsertionSort.sort(arr, beginIdx, len); return; } final int endIdx = beginIdx+len-1; final long pivot = getPivot(arr, beginIdx, len); final long lengths = threeWayPartitioning(arr, beginIdx, endIdx, pivot); final int lLen = (int)(lengths>>32); final int rLen = (int)lengths; threeWayQuickSort(arr, beginIdx, lLen); threeWayQuickSort(arr, endIdx-rLen+1, rLen); }
and run the test again:
arr[i]=rnd.nextInt(arr.length) | arr[i]=rnd.nextInt(arr.length/100) | |
Java 6 Arrays.sort | 1654ms | 935ms |
basicQuickSort | 1431ms | 2570ms |
basicQuickSort with ‘better’ pivot | 1365ms | 2482ms |
Three-way partitioning Quicksort | 1330ms | 829ms |
Three-way partitioning Quicksort with Insertion sort | 1155ms | 818ms |
now standard library looks just awful. It looks now that all is said and done. But it in reality that’s not the end of the story and there is something else to talk about.
Dual-pivot Quicksort
Moving forward, I found that Java 7 is much more advanced and performs much faster than Java 6 version and outperforms all previous tests:
arr[i]=rnd.nextInt(arr.length) | arr[i]=rnd.nextInt(arr.length/100) | |
Java 6 Arrays.sort | 1654ms | 935ms |
Java 7 Arrays.sort | 951ms | 764ms |
basicQuickSort | 1431ms | 2570ms |
basicQuickSort with ‘better’ pivot | 1365ms | 2482ms |
Three-way partitioning Quicksort | 1330ms | 829ms |
Three-way partitioning Quicksort with Insertion sort | 1155ms | 818ms |
public static void dualPivotQuicksort(long arr[], int beginIdx, int len) { if ( len < 2 ) return; final int endIdx = beginIdx+len-1; long pivot1 = arr[beginIdx]; long pivot2 = arr[endIdx]; if ( pivot1 == pivot2 ) { final long lengths = QuickSort.threeWayPartitioning(arr, beginIdx, endIdx, pivot1); final int lLen = (int)(lengths>>32); final int rLen = (int)lengths; dualPivotQuicksort3(arr, beginIdx, lLen); dualPivotQuicksort3(arr, endIdx-rLen+1, rLen); } else { if ( pivot1 > pivot2 ) { long tmp = pivot1; pivot1 = pivot2; pivot2 = tmp; Utils.swap(arr, beginIdx, endIdx); } int l = beginIdx; int r = endIdx; int p = beginIdx; while ( p <= r ) { if ( arr[p] < pivot1 ) { Utils.swap(arr, l++, p++); } else if ( arr[p] > pivot2 ) { while ( arr[r] > pivot2 && r > p ) { --r; } Utils.swap(arr, r--, p); } else { ++p; } } if ( arr[l] == pivot1 ) ++l; if ( arr[r] == pivot2 ) --r; dualPivotQuicksort3(arr, beginIdx, l-beginIdx); dualPivotQuicksort3(arr, l, r-l+1); dualPivotQuicksort3(arr, r+1, endIdx-r); } }
First code picks up two pivots. If pivots are the same, it means we have just one pivot and in that case we can used three-way method for partitioning. If pivots are different, then partitioning process will look like this:
Scanning pointer “p” is moving from the beginning of array. If current element is “<> pivot1″, then r-th element is swapped with p-th and “r” pointer is moved to next element backwards. All stops when “p” becomes less than “r”. After partitioning, array will look like this:
- Quicksort Wikipedia article
- Dual-Pivot QuickSort
- Quicksort Is Optimal presentation by Robert Sedgewick & Jon Bentley
- MIT lecture about quicksort
Software ArchitectureThis guide will introduce you to the world of Software Architecture! This 162 page guide will cover topics within the field of software architecture including: software architecture as a solution balancing the concerns of different stakeholders, quality assurance, methods to describe and evaluate architectures, the influence of architecture on reuse, and the life cycle of a system and its architecture. This guide concludes with a comparison between the professions of software architect and software engineer. |
In Java TimSort is the default sorting for all data types
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Collections.java#Collections.sort%28java.util.List%29
I have several questions related to
microbenchmarking in this article. For example, did you take in account fact, that under
the hood there is GC working? Also JIT should be taken in consideration – in
server mode it optimizes, compiles and swaps hot code after 10000 method
invocations (+ time of compilation & swap of the native code). Another
aspect – did you use System.currentTimeMillis(); or System.nanoTime() to gather
execution times? Last thing – execution time is only one of the metrics in
benchmarks. What about memory consumption?
Generally, there is a pretty good article
about benchmarking in Java:
http://www.javacodegeeks.com/2011/09/java-micro-benchmarking-how-to-write.html