Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
JavaScript Implementation of Quick Sort (Hoare Partition Scheme)
// https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme
function quickSort(arr, left, right) {
if (left < right) {
const index = partition(arr, left, right);
quickSort(arr, left, index);
quickSort(arr, index + 1, right);
}
}
function partition(arr, left, right) {
const pivot = arr[Math.floor((left+right)/2)];
while (true) {
while (arr[left] < pivot) {
left++;
}
while (arr[right] > pivot) {
right--;
}
if (left >= right) {
return right;
}
swap(arr, left, right);
}
}
function swap(arr, i, j) {
const tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
let arr = [9, 4, 1, 6, 7, 3, 8, 2, 5];
quickSort(arr, 0, arr.length - 1);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.