{{ message }}

Instantly share code, notes, and snippets.

# claudiahdz/QuickSort.js

Last active Jul 29, 2020
 // 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 commented Aug 25, 2019 • edited

 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 :)