Javascript Quicksort Comparisons
JavaScript performance comparison
Preparation code
<script>
Benchmark.prototype.setup = function() {
var arr = [];
var n = 200000; //array size we are sorting
for (var i = 0; i < n; i++) {
arr.push(parseInt(Math.random() * 10000));
}
/********************************************* SHUFFLE *****************************************************************/
//Fisher-Yates...aka..Knuth Shuffle
function shuffle(arr) {
var currentIndex = arr.length;
var temporaryValue;
var randomIndex;
// While there remain elements to shuffle...
while (0 !== currentIndex) {
// Pick a remaining element...
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex -= 1;
// And swap it with the current element.
temporaryValue = arr[currentIndex];
arr[currentIndex] = arr[randomIndex];
arr[randomIndex] = temporaryValue;
}
return arr;
}
/*********************************** RECURSIVE QUICK SORT *************************************************************/
var StandardRecursiveQuicksort = (function() {
var standardRecursiveQS = {};
standardRecursiveQS.sort = function(arr) {
if (arr.length <= 1) {
return arr;
}
return recursiveQuickSort(arr, 0, arr.length - 1);
}
function recursiveQuickSort(arr, left, right) { //partition arrays so that everything to the left of pivot is less then pivot, and everything to the right is greater then pivot
var i = left;
var j = right;
var tmp;
var pivotidx = (left + right) / 2;
var pivot = parseInt(arr[pivotidx.toFixed()]);
/* partition */
while (i <= j) {
while (parseInt(arr[i]) < pivot)
i++;
while (parseInt(arr[j]) > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
/* recursion */
if (left < j)
recursiveQuickSort(arr, left, j);
if (i < right)
recursiveQuickSort(arr, i, right);
return arr;
}
return standardRecursiveQS;
}());
/**********************************************************************************************************************/
/*************************************** Three Way Partition Quicksort ************************************************/
var ThreeWayPartitionQuicksort = (function() {
var ThreeWayPartionQuicksortModule = {};
//Private Variables
var CUTOFF = 8; // cutoff to insertion sort, must be >= 1
ThreeWayPartionQuicksortModule.sort = function( a, lo, hi) { //Public function
if(typeof lo == "undefined" && typeof hi === "undefined"){
this.sort(a, 0, a.length - 1);
} else{
var N = hi - lo + 1;
// cutoff to insertion sort
if (N <= CUTOFF) {
insertionSort(a, lo, hi);
return;
}
// use median-of-3 as partitioning element
else if (N <= 40) {
var m = median3(a, lo, lo + N/2, hi);
exch(a, m, lo);
}
// use Tukey ninther as partitioning element
else {
var eps = N/8; //TODO: verify these come out as integers
var mid = lo + N/2;
var m1 = median3(a, lo, lo + eps, lo + eps + eps);
var m2 = median3(a, mid - eps, mid, mid + eps);
var m3 = median3(a, hi - eps - eps, hi - eps, hi);
var ninther = median3(a, m1, m2, m3);
exch(a, ninther, lo);
}
// Bentley-McIlroy 3-way partitioning
var i = lo, j = hi+1;
var p = lo, q = hi+1;
var v = a[lo];
while (true) {
while (less(a[++i], v))
if (i == hi) break;
while (less(v, a[--j]))
if (j == lo) break;
// pointers cross
if (i == j && eq(a[i], v))
exch(a, ++p, i);
if (i >= j) break;
exch(a, i, j);
if (eq(a[i], v)) exch(a, ++p, i);
if (eq(a[j], v)) exch(a, --q, j);
}
i = j + 1;
for (var k = lo; k <= p; k++) exch(a, k, j--);
for (var k = hi; k >= q; k--) exch(a, k, i++);
this.sort(a, lo, j);
this.sort(a, i, hi);
}
}
// sort from a[lo] to a[hi] using insertion sort
function insertionSort( a, lo, hi) {
for (var i = lo; i <= hi; i++)
for (var j = i; j > lo && less(a[j], a[j-1]); j--)
exch(a, j, j-1);
}
// return the index of the median element among a[i], a[j], and a[k]
function median3( a, i, j, k) {
return (less(a[i], a[j]) ?
(less(a[j], a[k]) ? j : less(a[i], a[k]) ? k : i) :
(less(a[k], a[j]) ? j : less(a[k], a[i]) ? k : i));
}
/***********************************************************************
* Helper sorting functions
***********************************************************************/
// is v < w ?
function less(v, w) {
return (v < w); //java version uses compareto
}
// does v == w ?
function eq(v, w) {
return (v == w); //java version uses compareto
}
// exchange a[i] and a[j]
function exch(a, i, j) {
var swap = a[i];
a[i] = a[j];
a[j] = swap;
}
return ThreeWayPartionQuicksortModule;
}());
/**********************************************************************************************************************/
/*************************************** Dual Pivot QuickSort *********************************************************/
var DualPivotQuicksort = (function() {
var dualPivotQS = {};
dualPivotQS.sort = function(arr, fromIndex, toIndex) {
if(fromIndex === undefined && toIndex === undefined){
this.sort(arr, 0, arr.length);
} else{
rangeCheck(arr.length, fromIndex, toIndex);
dualPivotQuicksort(arr, fromIndex, toIndex - 1, 3);
}
return arr;
}
function rangeCheck(length, fromIndex, toIndex) {
if (fromIndex > toIndex) {
console.error("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
}
if (fromIndex < 0) {
console.error(fromIndex);
}
if (toIndex > length) {
console.error(toIndex);
}
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function dualPivotQuicksort( arr, left, right, div) {
var len = right - left;
if (len < 27) { // insertion sort for tiny array
for (var i = left + 1; i <= right; i++) {
for (var j = i; j > left && arr[j] < arr[j - 1]; j--) {
swap(arr, j, j - 1);
}
}
return;
}
var third = Math.floor(len / div); //TODO: check if we need to round up or down or just nearest
// "medians"
var m1 = left + third;
var m2 = right - third;
if (m1 <= left) {
m1 = left + 1;
}
if (m2 >= right) {
m2 = right - 1;
}
if (arr[m1] < arr[m2]) {
swap(arr, m1, left);
swap(arr, m2, right);
}
else {
swap(arr, m1, right);
swap(arr, m2, left);
}
// pivots
var pivot1 = arr[left];
var pivot2 = arr[right];
// pointers
var less = left + 1;
var great = right - 1;
// sorting
for (var k = less; k <= great; k++) {
if (arr[k] < pivot1) {
swap(arr, k, less++);
}
else if (arr[k] > pivot2) {
while (k < great && arr[great] > pivot2) {
great--;
}
swap(arr, k, great--);
if (arr[k] < pivot1) {
swap(arr, k, less++);
}
}
}
// swaps
var dist = great - less;
if (dist < 13) {
div++;
}
swap(arr, less - 1, left);
swap(arr, great + 1, right);
// subarrays
dualPivotQuicksort(arr, left, less - 2, div);
dualPivotQuicksort(arr, great + 2, right, div);
// equal elements
if (dist > len - 13 && pivot1 != pivot2) {
for (var k = less; k <= great; k++) {
if (arr[k] == pivot1) {
swap(arr, k, less++);
}
else if (arr[k] == pivot2) {
swap(arr, k, great--);
if (arr[k] == pivot1) {
swap(arr, k, less++);
}
}
}
}
// subarray
if (pivot1 < pivot2) {
dualPivotQuicksort(arr, less, great, div);
}
}
return dualPivotQS;
}());
/**********************************************************************************************************************/
};
Benchmark.prototype.teardown = function() {
shuffle(arr);
};
</script>
Test runner
Warning! For accurate results, please disable Firebug before running the tests. (Why?)
Java applet disabled.
Test | Ops/sec | |
---|---|---|
Quicksort 8 - assignment instead of push
|
|
pending… |
Quicksort 7 - median pivot
|
|
pending… |
Quicksort 6 - reverse loop
|
|
pending… |
Default Recursive Javascript Quicksort
|
|
pending… |
Three Way Partition Javascript Quicksort
|
|
pending… |
Dual Pivot Javascript Quicksort
|
|
pending… |
Default Javascript Sort
|
|
pending… |
Quicksort 5
|
|
pending… |
Compare results of other browsers
Revisions
You can edit these tests or add even more tests to this page by appending /edit
to the URL.
- Revision 1: published Stan
- Revision 2: published stacey reiman
- Revision 3: published stacey reiman
- Revision 4: published stacey reiman
- Revision 5: published stacey reiman
- Revision 6: published Mark
0 Comments