Instantly share code, notes, and snippets.

Embed
What would you like to do?
QuickSort In Place (in JavaScript)
// quicksort using new arrays is easy, but surprisingly, there weren't too many examples
// in javascript of in-place quick sort...
// the outer function is simply just a wrapper that copies the original array;
// you can just use lines 12-37 if preserving the original array isn't important
function quickSortInPlace(unsortedArray) {
var unsorted = unsortedArray.slice(); // copy the original array
// lb, rb - left bound, right bound
function qSort(unsorted, lb, rb) {
if(typeof lb === 'undefined') { lb = 0; }
if(typeof rb === 'undefined') { rb = unsorted.length-1; }
if(lb < rb) {
var pivot = unsorted[Math.floor((lb+rb)/2)];
var l = lb, r = rb; // index variables that travel from either end
var tmpSwap;
// what some people call the partitioning
while(l < r) {
while(unsorted[l] < pivot) { l++; }
while(pivot < unsorted[r]) { r--; }
if(l <= r) {
tmpSwap = unsorted[l];
unsorted[l] = unsorted[r];
unsorted[r] = tmpSwap;
l++;
r--;
}
}
qSort(unsorted, lb, r);
qSort(unsorted, l, rb);
}
}
qSort(unsorted);
return unsorted;
}
@ftripier

This comment has been minimized.

ftripier commented Sep 9, 2013

Please instantiate qSort in global scope, and then simply call it using parameters from quickSortInPlace's local scope.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment