Quick Sort Flashcards
Quick sort is a highly efficient ____-and-_____ sorting algorithm
divide-and-conquer
Quick sort partitions the around a pivot value that yields _____ < ______ <_______
L < pivot < G
The mechanism takes ___ elements less than P and ____ elements greater than P. Then applies the ___-and-_____ approach to solve the subproblems. Finally, it _____ the solutions of the subproblem to form the final solution
L, G, divide-and-conquer, merges
Quick sort’s efficiency heavily depends on the choice of the _____ element.
pivot
What is a pivot that is randomly selected?
random pivot
What is a pivot that is the first entry of the list?
first element pivot
What is a pivot that takes the median of the first, middle, and last element in the list?
median-of-three pivot
What is the best pivot to use for quick sort? Why?
median-of-three because it uses O(n log n)
What is the best-case time complexity for quick sort?
O(n log n)
What is the worst-case time complexity for quick sort? (depending on the pivot chosen)
O(n^2)
What is the space complexity for quick sort?
O(log n)
For space complexity, quick sort uses _____ stack.
recursion
Does quick sort use frequent swaps for partitioning?
yes!
Merge sort is a _________ sorting method.
recursive
