Skip to content

Instantly share code, notes, and snippets.

@nikcorg
Created March 15, 2012 12:19
Show Gist options
  • Save nikcorg/2043935 to your computer and use it in GitHub Desktop.
Save nikcorg/2043935 to your computer and use it in GitHub Desktop.
QuickSort (recursive, wasteful) in JavaScript
var n = 100,
arr = (function (l, r, i) { for (i = 0; i < l; r.push(i++)); return r;}(n, []));
// http://en.wikipedia.org/wiki/Quicksort
function quicksort(arr) {
var pivot,
pi = Math.floor(Math.random() * arr.length), // Random pivot index
below = [],
above = [],
i, l;
if (arr.length < 2) return arr;
pivot = arr.splice(pi, 1).pop();
for (i = 0, l = arr.length; i < l; i++) {
if (arr[i] < pivot) {
below.push(arr[i]);
} else {
above.push(arr[i]);
}
}
return [].concat(quicksort(below), pivot, quicksort(above));
}
// The shuffle-function can be found at https://gist.github.com/2043791
quicksort(shuffle(arr));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment