Given a non-empty array of unique integers, sort the array in ascending order using the QuickSort algorithm.
QuickSort is a popular and efficient sorting algorithm comparable to Merge Sort and Heap Sort.
QuickSort is a recursive algorithm and consists of two major steps:
- Selecting a "pivot element".
- "Partitioning" elements in the array relative to selected pivot element.
- We are going to arbitrarily choose an element from the array to be our pivot element. You can think of the pivot element as a "baseline" that we will use to compare the relative order of other elements in the array. QuickSort performs best when the pivot element is roughly the median of the array. It performs worst when the pivot element is the greatest or smallest element in the array. The reason is because when the pivot is the median, the array gets partioned roughly in half on each recursive call. But when the pivot is the greatest or smallest element, the array gets partioned unevenly, which leads to more recursive calls.
- We will traverse our array from left to right and right to left (while left bound <= right bound) swapping the position of elements that are "out of order". An element on the left is out of order if it's greater than our pivot element. An element on the right is out of order if it's less than our pivot element. We will start by looking from left to right for the first element that is greater than our pivot element, call it "A". Then, we will look from right to left for the first element that is less than our pivot element, call it "B". If the index of "A" is less than the index of "B" (i.e. "A" comes before "B" in the array), we will swap "A" and "B". After each swap, we keep traversing the array until our left and right bounds cross. As we swap elements, the elements that are less than the pivot will be grouped to the left and elements greater than the pivot will ge grouped to the right. It's important to note that each partion will NOT necessarily be individually sorted yet. (Although it could potentially be.)
- After partioning the array into elements greater than and smaller than the pivot element, we will recurse on each partition and repeat the process.
const partition = (array, left, right, pivot) => {
// swap elements while
// left bound <= right bound.
while (left <= right) {
// move left pointer until we find
// an element that is greater than our pivot element.
// this element will get "pushed" to the right.
while (array[left] < pivot) left++
// move right pointer until we find
// an element that is less than our pivot element.
// this element will get "pushed" to the left.
while (array[right] > pivot) right--
// only swap elements if
// left bound <= right bound
// (this prevents swapping elements that were already swapped.)
if (left <= right) {
// after swapping elements, move left and right
// pointers towards each other.
[array[left], array[right]] = [array[right], array[left]]
left++
right--
}
}
// after our left and right pointers cross (i.e. left > right),
// the left pointer will mark the division between
// elements greater than and less than the pivot element.
return left
}
const quickSort = (array, left = 0, right = array.length - 1) => {
// base case:
// we are done when the
// left and right bounds meet.
if (left >= right) return
// arbitrarily choose a pivot element.
// in this case, we are choosing the
// middle element of the current partition
// (but the pivot element can be any element in the array.)
const pivot = array[Math.floor((left + right) / 2)]
// partition the array around our chosen pivot element.
// after each partition, elements greater
// than the pivot element will accumulate to the right of the array,
// and elements less than the pivot element will accumulate to the left.
// the value of `index` marks this division.
const index = partition(array, left, right, pivot)
// recurse on each of the two partitions:
// 1) the partition with elements greater than the pivot element.
// 2) the partition with elements less than the pivot element.
// (the partition in which the pivot element itself
// lands depends on the implementation of the partition function
// and is not an important detail.)
quickSort(array, left, index - 1)
quickSort(array, index, right)
}
const array = [15, 3, 2, 1, 9, 5, 7, 8, 6]
quickSort(array)
console.log(array) // [1, 2, 3, 5, 6, 7, 8, 9, 15]- Best/Average case: O(n * log(n)) where n is the number of elements in the array.
- As I mentioned before, QuickSort is a sorting algorithm comparable to Merge Sort. Since both of these are comparison-based algorithms, they will run in O(n * log(n)) time at best.
- Worst case: O(n^2) where n is the number of elements in the array.
- In the worst case (where we get unlucky and choose bad pivots) the runtime for QuickSort is not so quick. This is due to uneven partitions.
O(log(n)) where n is the number of elements in the array.
Sorting for QuickSort is done in place. However, we do recurse in a "depth-firt" manner. Since we partition the array on each iteration, and only recurse on one partition at a time, we only have at most log(n) calls in the call stack at one time.
- Video explanation of QuickSort (with visuals and code implementation): https://www.youtube.com/watch?v=SLauY6PpjW4
- Alternate video explanation (with space & time complexity analysis): https://www.youtube.com/watch?v=uXBnyYuwPe8
- AlgoExpert "QuickSort" problem (try it yourself!): https://www.algoexpert.io/questions/Quick%20Sort
- Repl.it with code above: https://repl.it/join/nznaedzm-ecanals07
- Wikipedia article on QuickSort: https://en.wikipedia.org/wiki/Quicksort