Quick Sort
Chapter 18
Best Possible Performance
Lower Bound on Comparison-Based Sorting
Can we do better than
What is the best we can do?
Comparison Tree
Comparison tree: graph used to trace the execution of a comparison-based algorithm.
- Let
be a list of distinct elements, where . For any and , where , , either or .
- Let
Binary tree: each comparison has two outcomes.
Terminology of Comparison Trees
Node: represents a comparison
Labeled as
(comparison of with ) If
, follow the left branch; otherwise, follow the right branch.
Leaf: represents the final ordering of the nodes
Root: the top node
Branch: line that connects two nodes
Path: sequence of branches from one node to another
Comparison Tree for Sorting 3 Items
A unique permutation of the elements of
is associated with each root-to-leaf path. - Because the sort algorithm only moves the data and makes comparisons.
For a list of
elements, , there are different permutations - Any of these might be the correct ordering of
.
- Any of these might be the correct ordering of
Thus, the tree must have at least
leaves.
Lower Bound on Comparison-Based Sorting
Theorem: Any sorting algorithm that sorts a list of
We won’t prove this theorem, but unlike the previous algorithms discussed, there are algorithms that, on average, are
Introduction
Quick sort: uses the divide-and-conquer technique.
The list is partitioned into two sub-lists.
Each sub-list is then sorted.
Sorted sub-lists are combined into one list in such a way that the combined list is sorted.
All the sorting work occurs when partitioning the list.
Pivot Element
Choose an element to split the list pivot element.
Move elements less than the pivot value to the lower sub-list.
Move elements greater than the pivot value to the upper sub-list.
The pivot can be chosen in several ways.
Ideally, the pivot will divide the list into two sub-lists of near-equal size.
Quick Sort: Example
See the lecture video above for the full selection-sort example.
Analysis of Quick Sort
| Algorithm | Comparisons | Swaps |
|---|---|---|
| Bubble Sort | ||
| Selection Sort | ||
| Array-Based Insertion Sort | ||
| Linked-List Insertion Sort | ||
| Quick Sort: Average Case | ||
| Quick Sort: Worst Case |
| Quick Sort | Comparisons | Swaps |
|---|---|---|
| Average Case | ||
| Worst Case |
Worst Case of Quick Sort
If the chosen pivot is always the smallest or largest value, Quick Sort behaves like a Selection Sort.
Quick Sort Optimizations
Choose a better pivot.
Median of three: first, middle, last elements.
Randomly select a pivot.
Use a different algorithm for small sub-lists.
Insertion sort is best for lists of 10 or fewer elements.
The overhead of the recursive calls is greater than the cost of the insertion sort.
Use fancy partitioning techniques.
Hoare's partitioning: Traverse the list from both sizes, swapping smaller elements to the left and larger elements to the right.
Dual-Pivot partitioning: Partitions the list into three sub-lists.