Skip to content

Instantly share code, notes, and snippets.

@zbicin
Last active October 7, 2021 17:09
Show Gist options
  • Save zbicin/9738448214e5a87245a27f6e2300a86d to your computer and use it in GitHub Desktop.
Save zbicin/9738448214e5a87245a27f6e2300a86d to your computer and use it in GitHub Desktop.
QuickSort implementation in JavaScript
function quickSort(arr, start = 0, end = arr.length - 1) {
if (start < end) {
const sortedIndex = partition(arr, start, end);
quickSort(arr, start, sortedIndex-1);
quickSort(arr, sortedIndex+1, end);
}
}
function swap(arr, a, b) {
let temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
function partition(arr, start, end) {
let pivotIndex = start + Math.ceil((end - start) / 2); // or simply end
const pivot = arr[pivotIndex];
let sortedIndex = start - 1;
for(let j = start; j <= end; j++) {
const currentValue = arr[j];
if(currentValue < pivot) {
sortedIndex++;
swap(arr, sortedIndex, j);
if(sortedIndex === pivotIndex) {
pivotIndex = j;
} else if(j === pivotIndex) {
pivotIndex = sortedIndex;
}
}
}
sortedIndex++;
swap(arr, sortedIndex, pivotIndex);
return sortedIndex;
}
/*
const array = [10, 80, 30, 90, 40, 50, 70];
quickSort(array);
console.log(array);
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment