Skip to content

Instantly share code, notes, and snippets.

@claudiahdz
Last active July 31, 2022 01:48
Show Gist options
  • Star 19 You must be signed in to star a gist
  • Fork 5 You must be signed in to fork a gist
  • Save claudiahdz/39a86084edaaabe7fc17c321c0bb6896 to your computer and use it in GitHub Desktop.
Save claudiahdz/39a86084edaaabe7fc17c321c0bb6896 to your computer and use it in GitHub Desktop.
// 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,
index
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) {
i++
}
// Move right pointer to the left until the value at the
// right is less than the pivot value
while(arr[j] > pivot) {
j--
}
// 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
i++
j--
}
}
return i
}
@roblevintennis
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