Skip to content

Instantly share code, notes, and snippets.

@cmdoptesc
Created September 9, 2013 06:49
Show Gist options
  • Save cmdoptesc/6492231 to your computer and use it in GitHub Desktop.
Save cmdoptesc/6492231 to your computer and use it in GitHub Desktop.
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
Copy link

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