Skip to content

Instantly share code, notes, and snippets.

@greathmaster
Created July 22, 2020 21:28
Show Gist options
  • Save greathmaster/e2af585d29deef18d9b7259f0eabf370 to your computer and use it in GitHub Desktop.
Save greathmaster/e2af585d29deef18d9b7259f0eabf370 to your computer and use it in GitHub Desktop.
Variations on a theme by Quicksort
//Recursive Quicksort using Lomuto's partitioning method
function lomutosPartition(array, start, end) {
let i = start;
let pivot = array[end]
for(let j = start; j < end; j++) {
if(pivot > array[j]) {
[array[j], array[i]] = [array[i], array[j]];
i++;
}
}
[array[i], array[end]] = [array[end], array[i]]
return i;
}
function quickLomuto(array, start, end) {
if(end - start <= 1) {
return;
}
let pivotIndex = lomutosPartition(array, start, end)
quickLomuto(array, pivotIndex + 1, end)
quickLomuto(array, start, pivotIndex - 1)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment