Quicksort Flashcards
1
Q
Stable Sorting
A
If the same element is present multiple times, then they retain the original relative order of positions.
1
Q
In place sorting
A
Sorting of a data structure does not require any external data structure for storing the intermediate steps.
2
Q
Quicksort is ___, but not ___.
A
In place, but not stable.
3
Q
Mergesort is ___, but not in place.
A
Stable, but not in place.
4
Q
Quicksort Worst Case
A
θ(n^2)
5
Q
Quicksort Best Case Partitioning
A
T(n) = θ(n log n)
6
Q
Quicksort Average Case
A
θ(n log n)
7
Q
Pivot Selection Strategies
A
First or Last Element
Random
Median of 3 (left, right, and center)
Median of Medians.
8
Q
Do not use quicksort recursively for:
A
arrays of size smaller than some threshold.
