QuickSort.java
Quick sort has O(nlogn) performance, on average, is a few times faster than merge sort, however, at bad time, it can stuck at O(n^2) performance -- when n is large, O(n^2) means practically never sort out.
0
1
2
3
4
5
6
7
8
9
stack content:
function shuffle(a) {
for (let i = a.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[a[i], a[j]] = [a[j], a[i]];
}
return a;
}
function sort_quick(a) {
displayArray(a, 0, a.length - 1);
shuffle(a);
displayArray(a, 0, a.length - 1);
// Eliminate dependence on input.
quickSort(a, 0, a.length - 1);
}
function partition(a, lo, hi) {
// Partition into a[lo..i-1], a[i], a[i+1..hi].
var i = lo;
var j = hi+1;
// left and right scan indices
var v = a[lo];
// partitioning item
while (true) {
// Scan right, scan left, check for scan complete, and exchange.
while (a[++i] < v) if (i == hi) break;
while (v < a[--j]) if (j == lo) break;
if (i >= j) break;
exch(a, i, j);
}
exch(a, lo, j); // Put v = a[j] into position
return j; // with a[lo..j-1] <= a[j] <= a[j+1..hi].
}
function quickSort(a, lo, hi) {
if (hi <= lo) return;
var j = partition(a, lo, hi);
displayArray(a, j, j);
displayArray(a, lo, j-1);
quickSort(a, lo, j-1);
displayArray(a, lo, j-1);
// Sort left part a[lo .. j-1].
displayArray(a, j+1, hi);
quickSort(a, j+1, hi);
displayArray(a, j+1, hi);
// Sort right part a[j+1 .. hi].
}
Quick Sort trade off some stability for speed, it is faster than merge sort most of the time, but severely slower than merge sort in some rare cases.
Feel the algorithm
<Prev Next>
