Skip to content

Instantly share code, notes, and snippets.

Last active July 31, 2022 01:48
  • Star 19 You must be signed in to star a gist
  • Fork 5 You must be signed in to fork a gist
Star You must be signed in to star a gist
What would you like to do?
// Find a "pivot" element in the array to compare all other
// elements against and then shift elements before or after
// pivot depending on their values
function QuickSort(arr, left = 0, right = arr.length - 1) {
let len = arr.length,
if(len > 1) {
index = partition(arr, left, right)
if(left < index - 1) {
QuickSort(arr, left, index - 1)
if(index < right) {
QuickSort(arr, index, right)
return arr
function partition(arr, left, right) {
let middle = Math.floor((right + left) / 2),
pivot = arr[middle],
i = left, // Start pointer at the first item in the array
j = right // Start pointer at the last item in the array
while(i <= j) {
// Move left pointer to the right until the value at the
// left is greater than the pivot value
while(arr[i] < pivot) {
// Move right pointer to the left until the value at the
// right is less than the pivot value
while(arr[j] > pivot) {
// If the left pointer is less than or equal to the
// right pointer, then swap values
if(i <= j) {
[arr[i], arr[j]] = [arr[j], arr[i]] // ES6 destructuring swap
return i
Copy link

roblevintennis commented Aug 25, 2019

This is a cool gist and I really like how you've incorporated ES6 default params and destructoring into it!

I just did some studying on quick sort and referenced a few examples including this one, and, the Zakas article which I believe this was inspired by as are many other JavaScript implementations of quick sort I've came across. Interestingly, when I starting looking at the swaps, there will be cases where the left and right pointer are on same element, and will carry out an unnecessary swap due to the if(i <= j) conditional. I've found that if you change that to if(i < j) for the swap case, and then add another if (i === j) for the increment and decrement cases, it fixes that. Code is a bit more complex, but possibly it's an improvement. I hope you don't mind the random drive by comment :)

UPDATE: Ok, I feel silly, but after some more testing, it turns out without doing it the way Zakas has it as do you on line #48, you will infinite loop if you have duplicates in your input array!

I'll leave this comment for posterity in case someone else thinks they've found a clever optimization haha :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment