Skip to content

Instantly share code, notes, and snippets.

@N02870941 N02870941/quicksort.js
Last active Jul 28, 2019

Embed
What would you like to do?
/**
* Sorts an array of values. An optional 2 parameter comparator function is available
* to specify ordering. If no comparator is supplied, then the values will be sorted
* based on their primitive values via the Object.prototype.valueOf() function.
*/
function sort(array, comparator = (a, b) => a.valueOf() - b.valueOf()) {
quicksort(array, 0, array.length-1, comparator)
}
//------------------------------------------------------------------------------
/**
* Quicksort using Hoare partitioning scheme.
*/
function quicksort(a, lo, hi, compare) {
if (lo >= hi)
return
let i = lo
let j = hi
let r = Math.floor(Math.random() * ((hi+1) - lo) + lo)
let pivot = a[r]
while (i <= j) {
while (compare(a[i], pivot) < 0)
i++
while (compare(a[j], pivot) > 0)
j--
if (i <= j) {
[a[j], a[i]] = [a[i], a[j]]
i++
j--
}
}
if (lo < j)
quicksort(a, lo, j, compare)
if (i < hi)
quicksort(a, i, hi, compare)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.