Skip to content

Instantly share code, notes, and snippets.

@quisido
Last active April 17, 2019 07:14
Show Gist options
  • Save quisido/61d052d342a898ccd2738dff8befd517 to your computer and use it in GitHub Desktop.
Save quisido/61d052d342a898ccd2738dff8befd517 to your computer and use it in GitHub Desktop.
Implementing Quicksort in JavaScript
const quickSort = (
unsortedArray,
comparator = defaultComparator
) => {
// Create a sortable array to return.
const sortedArray = [ ...unsortedArray ];
// Recursively sort sub-arrays.
const recursiveSort = (start, end) => {
// If this sub-array is empty, it's sorted.
if (end - start < 1) {
return;
}
const pivotValue = sortedArray[end];
let splitIndex = start;
for (let i = start; i < end; i++) {
const sort = comparator(sortedArray[i], pivotValue);
// This value is less than the pivot value.
if (sort === -1) {
// If the element just to the right of the split index,
// isn't this element, swap them.
if (splitIndex !== i) {
const temp = sortedArray[splitIndex];
sortedArray[splitIndex] = sortedArray[i];
sortedArray[i] = temp;
}
// Move the split index to the right by one,
// denoting an increase in the less-than sub-array size.
splitIndex++;
}
// Leave values that are greater than or equal to
// the pivot value where they are.
}
// Move the pivot value to between the split.
sortedArray[end] = sortedArray[splitIndex];
sortedArray[splitIndex] = pivotValue;
// Recursively sort the less-than and greater-than arrays.
recursiveSort(start, splitIndex - 1);
recursiveSort(splitIndex + 1, end);
};
// Sort the entire array.
recursiveSort(0, unsortedArray.length - 1);
return sortedArray;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment