Quick Sort (JS Example)

Note: This is not a "professionally written" post. This is a post sharing personal notes I wrote down while preparing for FAANG interviews.

See all of my Google, Amazon, & Facebook interview study notes

Quicksort Breakdown

• Worst Complexity: n^2
• Average Complexity: n*log(n)
• Best Complexity: n*log(n)
• Method: Partitioning
• Class: Comparison Sort

Quicksort Explained

Quicksort is an in-place sorting algorithm. Developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be somewhat faster than merge sort and about two or three times faster than heapsort.

Quicksort Notes

• Inventor: Tony Hoare
• Unstable Sorting Algorithm
• Quicksort has a better space complexity than merge sort

Quicksort JavaScript Implementation

/*----------------------------------------------------------
 |   Quick Sort
 *----------------------------------------------------------
 |
 |   Time Complexity 
 |      . Best: O(n log n)
 |      . Aver: O(n log n)
 |      . Worst: O(n^2) 
 | 
 |   Space Complexity
 |      . O(log n)
 |
 |   Divide And Conquer Sort
 |   UnStable Sort
 |
 |   Better Space Complexity Than Merge Sort
 |   Time Complexity Worst Case Is Worse Than Merge Sort
 |   Merge Sort is A Stable Sort While Quick Sort is an Unstable Sort
 |
 */


const QuickSort = (items = [], left = [], right = []) => {
    if (items.length < 2) return items

    let [pivot, ...list] = items
    list.forEach(item => (item < pivot ? left : right).push(item))

    return [...QuickSort(left, [], []), pivot, ...QuickSort(right, [], [])]
}


module.exports = QuickSort

FAANG Study Resource: Cracking the Coding Interview
(Google Recommended)

My FAANG interview study notes

Quick Sort Github

Clean Code