Skip to content

Instantly share code, notes, and snippets.

@scwood
Last active April 16, 2018 19:46
Show Gist options
  • Select an option

  • Save scwood/0550cf04162a01908c1ed5f9f77a0b1d to your computer and use it in GitHub Desktop.

Select an option

Save scwood/0550cf04162a01908c1ed5f9f77a0b1d to your computer and use it in GitHub Desktop.
In place quicksort in JavaScript
function quickSort(arr) {
return quickSortAuxillary(arr, 0, arr.length - 1);
}
function quickSortAuxillary(arr, left, right) {
if (left < right) {
const middle = partition(arr, left, right);
quickSortAuxillary(arr, left, middle - 1);
quickSortAuxillary(arr, middle + 1, right);
}
}
function partition(arr, left, right) {
const pivot = arr[right];
let i = left;
for (let j = left; j < right; j++) {
if (arr[j] < pivot) {
swap(arr, i++, j);
}
}
if (arr[right] < arr[i]) {
swap(arr, i, right);
}
return i;
}
function swap(arr, i, j) {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment