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)
Top comments (2)
Thanks For sharing informative information. Dreamexch customer support