Created
September 9, 2013 06:49
-
-
Save cmdoptesc/6492231 to your computer and use it in GitHub Desktop.
QuickSort In Place (in JavaScript)
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
// 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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Please instantiate qSort in global scope, and then simply call it using parameters from quickSortInPlace's local scope.