DEV Community

Cover image for Quick Sort (JS Example)
Clean Code Studio
Clean Code Studio

Posted on • Updated on

Quick Sort (JS Example)

Twitter Follow

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
Enter fullscreen mode Exit fullscreen mode

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


My FAANG interview study notes

Quick Sort Github

Clean Code

Top comments (2)

Collapse
 
cleancodestudio profile image
Clean Code Studio
Collapse
 
bethlongoria profile image
BethLongoria

Thanks For sharing informative information. Dreamexch customer support