-
-
Save edwardbeckett/ed19753c0fd4a1caa6fb345f78e37218 to your computer and use it in GitHub Desktop.
Dual-Pivot Quicksort algorithm by Vladimir Yaroslavskiy, now with more input validation and support for (non-astral-plane-safe) string sorting (MIT License): https://web.archive.org/web/20151002230717/http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// https://web.archive.org/web/20141119215047/http://jsperf.com/javascript-quicksort-comparisons | |
// based on work from Vladimir Yaroslavskiy: https://web.archive.org/web/20151002230717/http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf | |
var dualPivotQuicksort = (function (Math, toString, undefined) { | |
'use strict'; | |
function swap(arr, i, j) { | |
var temp = arr[i]; | |
arr[i] = arr[j]; | |
arr[j] = temp; | |
} | |
function dualPivotQuicksort(arr, comp, left, right, div) { | |
var len = right - left, i, j; | |
if (len < 27) { // insertion sort for tiny array | |
for (i = left + 1; i <= right; i++) for (j = i; j > left && comp(arr[j], arr[j - 1]) < 0; j--) swap(arr, j, j - 1); | |
return arr; | |
} | |
var third = Math.floor(len / div), //TODO: check if we need to round up or down or just nearest | |
m1 = left + third, m2 = right - third; // 'medians' | |
if (m1 <= left) m1 = left + 1; | |
if (m2 >= right) m2 = right - 1; | |
if (comp(arr[m1], arr[m2]) < 0) { | |
swap(arr, m1, left); | |
swap(arr, m2, right); | |
} else { | |
swap(arr, m1, right); | |
swap(arr, m2, left); | |
} | |
var pivot1 = arr[left], pivot2 = arr[right], // pivots | |
less = left + 1, great = right - 1; // pointers | |
for (i = less; i <= great; i++) { // sorting | |
if (comp(arr[i], pivot1) < 0) swap(arr, i, less++); | |
else if (comp(arr[i], pivot2) > 0) { | |
while (i < great && comp(arr[great], pivot2) > 0) great--; | |
swap(arr, i, great--); | |
if (comp(arr[i], pivot1) < 0) swap(arr, i, less++); | |
} | |
} | |
var dist = great - less; // swaps | |
if (dist < 13) div++; | |
swap(arr, less - 1, left); | |
swap(arr, great + 1, right); | |
dualPivotQuicksort(arr, comp, left, less - 2, div); // subarrays | |
dualPivotQuicksort(arr, comp, great + 2, right, div); | |
if (dist > len - 13 && pivot1 !== pivot2) { // equal elements | |
for (i = less; i <= great; i++) { | |
if (arr[i] === pivot1) swap(arr, i, less++); | |
else if (arr[i] === pivot2) { | |
swap(arr, i, great--); | |
if (arr[i] === pivot1) swap(arr, i, less++); | |
} | |
} | |
} | |
if (comp(pivot1, pivot2) < 0) return dualPivotQuicksort(arr, comp, less, great, div); // subarray | |
return arr; | |
} | |
function compare(a, b) { | |
if (a < b) return -1; | |
if (a > b) return 1; | |
return 0; | |
} | |
function sort(array, comparison, fromIndex, toIndex) { // not astral-plane safe | |
var isStr = typeof array === 'string' || toString.call(array) === '[object String]', | |
arr = isStr ? array.split('') : array, len = arr.length || 0, | |
comp = typeof comparison === 'function' ? comparison : compare, | |
fromIdx = (typeof fromIndex === 'symbol' || toString.call(fromIndex) === '[object Symbol]') ? | |
0 : Math.min(fromIndex || 0, len) || 0, | |
toIdx = (typeof toIndex === 'symbol' || toString.call(toIndex) === '[object Symbol]') ? | |
0 : Math.min(toIndex || len, len); | |
if (toIdx !== toIdx) toIdx = len; // check against NaN | |
if (fromIdx < 0) fromIdx = Math.max(0, len + fromIdx); // support negative indexes | |
if (toIdx < 0) toIdx = Math.max(0, len + toIdx); | |
if (fromIdx < toIdx) dualPivotQuicksort(arr, comp, fromIdx, toIdx - 1, 3); | |
else if (toIdx < fromIdx) dualPivotQuicksort(arr, comp, toIdx, fromIdx - 1, 3); | |
else return array; | |
return isStr ? arr.join('') : arr; | |
} | |
sort.sort = sort; | |
return sort; | |
})(Math, Object.prototype.toString); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment