Skip to content

Instantly share code, notes, and snippets.

@cozzbie
Last active April 11, 2020 16:29
Show Gist options
  • Save cozzbie/0e6214a34d7fea5d891eab48970c220a to your computer and use it in GitHub Desktop.
Save cozzbie/0e6214a34d7fea5d891eab48970c220a to your computer and use it in GitHub Desktop.
// https://en.wikipedia.org/wiki/Quicksort
// Divide and Conquer type.
// Worst Case (Rare): O(n**2)
// Typical: O(NlogN)
const swap = (array, x, y) => {
array[x] = [array[y], array[y] = array[x]][0];
};
const partition = (array, p, r) => {
const pivot = array[r];
let i = p - 1;
for(let j = p; j < r; j++){
if(array[j] <= pivot){
i++;
swap(array, i, j);
}
}
swap(array, ++i, r);
return i;
};
const quicksort = (array, p, r) => {
if(p >= r) {
return;
}
const q = partition(array, p, r);
quicksort(array, p, q - 1);
quicksort(array, q + 1, r);
};
// Tail recursion
const tailquicksort = (array, p, r) => {
while(p < r){
const q = partition(array, p, r);
tailquicksort(array, p, q - 1);
p = q + 1;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment