CS61B
Lecture 32: Sorting III
¡ñ Quicksort Flavors vs. Mergesort
¡ñ Selection (Quick Select)
¡ñ Stability, Adaptiveness, and Optimization ¡ñ Shuffling
Partition Sort, a.k.a. Quicksort
Quicksorting N items: (Demo)
¡ñ Partition on leftmost item.
¡ñ Quicksort left half.
¡ñ Quicksort right half.
32
15
2
17
19
26
41
17
17
partition(32)
<= 32
in its place
>= 32
15
2
17
19
26
17
17
32
41
Run time is ¦¨(N log N) in the best case, ¦¨(N2) in the worst case, and ¦¨(N log N) in the average case.
datastructur.es
Avoiding the Worst Case: Question from Last Time
If pivot always lands somewhere ¡°good¡±, Quicksort is ¦¨(N log N). However, the very rare ¦¨(N2) cases do happen in practice, e.g.
¡ñ Bad ordering: Array already in sorted order (or almost sorted order).
¡ñ Bad elements: Array with all duplicates.
What can we do to avoid worst case behavior?
Recall, our version of Quicksort has the following properties:
¡ñ Leftmost item is always chosen as the pivot.
¡ñ Our partitioning algorithm preserves the relative order of <= and >= items.
6
8
3
1
2
7
4
3
1
2
4
6
8
7
datastructur.es
Avoiding the Worst Case: My Answers
What can we do to avoid running into the worst case for QuickSort?
Four philosophies:
1. Randomness: Pick a random pivot or shuffle before sorting.
2. Smarter pivot selection: Calculate or approximate the median. 3. Introspection: Switch to a safer sort if recursion goes to deep.
4. Preprocess the array: Could analyze array to see if Quicksort will be slow. No obvious way to do this, though (can¡¯t just check if array is sorted, almost sorted arrays are almost slow).
datastructur.es
Philosophy 1: Randomness (My Preferred Approach)
If pivot always lands somewhere ¡°good¡±, Quicksort is ¦¨(N log N). However, the very rare ¦¨(N2) cases do happen in practice, e.g.
¡ñ Bad ordering: Array already in sorted order.
¡ñ Bad elements: Array with all duplicates.
Dealing with bad ordering:
¡ñ Strategy #1: Pick pivots randomly.
¡ñ Strategy #2: Shuffle before you sort.
The second strategy requires care in partitioning code to
avoid ¦¨(N2) behavior on arrays of duplicates.
¡ñ Common bug in textbooks! See A level problems.
datastructur.es
Philosophy 2a: Smarter Pivot Selection (constant time pivot pick)
Randomness is necessary for best Quicksort performance! For any pivot selection procedure that is:
¡ñ Deterministic ¡ñ Constant Time
The resulting Quicksort has a family of dangerous inputs that an adversary could easily generate.
¡ñ See McIlroy¡¯s ¡°A Killer Adversary for Quicksort¡±
7
2
3
4
5
6
1
8
Dangerous input
datastructur.es
Philosophy 2b: Smarter Pivot Selection (linear time pivot pick)
Could calculate the actual median in linear time.
¡ñ ¡°Exact median Quicksort¡± is safe: Worst case ¦¨(N log N), but it is slower than Mergesort.
Raises interesting question though: How do you compute the median of an array? Will talk about how to do this later today.
datastructur.es
Philosophy 3: Introspection
Can also simply watch your recursion depth.
¡ñ If it exceeds some critical value (say 10 ln N), switch to mergesort.
Perfectly reasonable approach, though not super common in practice.
datastructur.es
Sorting Summary (so far)
Listed by mechanism:
¡ñ Selection sort: Find the smallest item and put it at the front.
¡ñ Insertion sort: Figure out where to insert the current item.
¡ñ Merge sort: Merge two sorted halves into one sorted whole.
¡ñ Partition (quick) sort: Partition items around a pivot.
Listed by memory and runtime:
Memory
Time
Notes
Heapsort
¦¨(1)
¦¨(N log N)
Bad caching (61C)
Insertion
¦¨(1)
¦¨(N2)
¦¨(N) if almost sorted
Mergesort
¦¨(N)
¦¨(N log N)
Random Quicksort
¦¨(log N) expected
¦¨(N log N) expected
Fastest sort
Quicksort Flavors
We said Quicksort is the fastest, but this is only true if we make the right decisions about:
¡ñ Pivot selection.
¡ñ Partition algorithm.
¡ñ How we deal with avoiding the worst case (can be covered by the above
choices).
We¡¯ll call this QuicksortL3S
Let¡¯s speed test Mergesort vs. Quicksort from last time, which had:
¡ñ Pivot selection: Always use leftmost.
¡ñ Partition algorithm: Make an array copy then do three scans for red, white,
and blue items (white scan trivially finishes in one compare).
¡ñ Shuffle before starting (to avoid worst case).
Quicksort vs. Mergesort
Pivot Selection Strategy
Partition Algorithm
Worst Case Avoidance Strategy
Time to sort 1000 arrays of 10000 ints
Mergesort
N/A
N/A
N/A
2.1 seconds
Quicksort L3S
Leftmost
3-scan
Shuffle
4.4 seconds
Quicksort didn¡¯t do so well!
Note: These are unoptimized versions of mergesort and quicksort, i.e. no switching to insertion sort for small arrays.
Tony Hoare¡¯s In-place Partitioning Scheme
Tony originally proposed a scheme where two pointers walk towards each other.
¡ñ Left pointer loves small items.
¡ñ Right pointer loves large items.
¡ñ Big idea: Walk towards each other, swapping anything they don¡¯t like.
¡ð End result is that things on left are ¡°small¡± and things on the right are ¡°large¡±.
Full details here: Demo
Using this partitioning scheme yields a very fast Quicksort.
¡ñ Though faster schemes have been found since.
¡ñ Overall runtime still depends crucially on pivot selection strategy!
Quicksort vs. Mergesort
Pivot Selection Strategy
Partition Algorithm
Worst Case Avoidance Strategy
Time to sort 1000 arrays of 10000 ints
Mergesort
N/A
N/A
N/A
2.1 seconds
Quicksort L3S
Leftmost
3-scan
Shuffle
4.4 seconds
Quicksort LTHS
Leftmost
Tony Hoare
Shuffle
1.7 seconds
Using Tony Hoare¡¯s two pointer scheme, Quicksort is better than mergesort!
¡ñ More recent pivot/partitioning schemes do somewhat better.
¡ð Best known Quicksort uses a two-pivot scheme.
¡ð Interesting note, this version of Quicksort was introduced to the world
by a previously unknown guy, in a Java developers forum (Link).
Note: These are unoptimized versions of mergesort and quicksort, i.e. no switching to insertion sort for small arrays.
What If We Don¡¯t Want Randomness?
Our approach so far: Use randomness to avoid worst case behavior, but some people don¡¯t like having randomness in their sorting routine.
Another approach: Use the median (or an approximation) as our pivot.
This is what we¡¯ve been using.
Four philosophies:
1. Randomness: Pick a random pivot or shuffle before sorting.
2. Smarter pivot selection: Calculate or approximate the median.
3. Introspection: Switch to a safer sort if recursion goes to deep.
4. Try to cheat: If the array is already sorted, don¡¯t sort (this doesn¡¯t work).
Philosophy 2a: Smarter Pivot Selection (linear time pivot pick)
Goal: Come up with an algorithm for finding the median of an array. Bonus points if your algorithm takes linear time.
¡ñ Create a double ended queue. If the value is ¡°smaller¡±, put it on the left side, if ¡°larger¡±, put it on the right side. Requires pivot.
¡ñ Use the quartile finder from the past midterm.
¡ð You create a min heap and a max heap, and insert some yadda yadda. It¡¯s
hard. This was an A/A+ level algorithm design problem. Try and devise it
later if you¡¯d like. N log N.
¡ñ Have an array of 5 items. The middle one is current ¡°median¡±. The one to the
left of the median is guaranteed to be the nex tsmallest, and the one to the irght isguaranteed to be the next largest. The first item is the number of items below the median and the last item is the number of both. [too complicated ofr lecture]
¡ñ Build a balanced binary search tree,a nd take the root — this only works if the
tree is perfectly balanced.
Philosophy 2a: Smarter Pivot Selection (linear time pivot pick)
The best possible pivot is the median.
¡ñ Splits problem into two problems of size N/2.
Obvious approach: Just calculate the actual median and use that as pivot. ¡ñ But how?
Goal: Come up with an algorithm for finding the median of an array. Bonus points if your algorithm takes linear time.
Your answer:
Median Identification
Is it possible to find the median in ¦¨(N) time?
¡ñ Yes! Use ¡®BFPRT¡¯ (called PICK in original paper).
¡ñ Algorithm developed in 1972 by a team including my former TA, Bob Tarjan
(well before I was born).
¡ñ In practice, rarely used.
Historical note: The authors of this paper include FOUR Turing Award winners (and Pratt is no slouch!)
Let¡¯s see how Exact Median Quicksort performs.
Quicksort vs. Mergesort
Pivot Selection Strategy
Partition Algorithm
Worst Case Avoidance Strategy
Time to sort 1000 arrays of 10000 ints
Worst Case
Mergesort
N/A
N/A
N/A
2.1 seconds
¦¨(N log N)
Quicksort L3S
Leftmost
3-scan
Shuffle
4.4 seconds
¦¨(N2)
Quicksort LTHS
Leftmost
Tony Hoare
Shuffle
1.7 seconds
¦¨(N2)
Quicksort PickTH
Exact Median
Tony Hoare
Exact Median
10.0 seconds
¦¨(N log N)
Quicksort using PICK to find the exact median (Quicksort PickTH) is terrible!
¡ñ Cost to compute medians is too high.
¡ñ Have to live with worst case ¦¨(N2) if we want good practical performance.
Note: These are unoptimized versions of mergesort and quicksort, i.e. no switching to insertion sort for small arrays.
Quick Select
The Selection Problem
Computing the exact median would be great for picking an item to partition around. Gives us a ¡°safe quick sort¡±.
¡ñ Unfortunately, it turns out that exact median computation is too slow.
However, it turns out that partitioning can be used to find the exact median.
¡ñ The resulting algorithm is the best known median identification algorithm.
Quick Select
Goal, find the median: Partition, pivot lands at 2.
¡ñ Not the median. Why?
¡ñ So what next? Partition right subproblem, median can¡¯t be to the left!
Now pivot lands at 6.
¡ñ Not the median.
Pivot lands at 4. Are we done? ¡ñ Yep, 9/2 = 4.
9
550
14
6
10
5
330
817
913
6
5
9
550
14
10
330
817
913
4
5
550
14
10
330
817
913
4
5
14
10
330
550
817
913
4
5
14
10
330
4
4
5
4
5
10
14
330
4
4
5
Worst case performance?
What is the worst case performance for Quick Select? Give an array that causes this worst case (assuming we always pick leftmost item as pivot).
Worst case performance?
What is the worst case performance for Quick Select? Give an array that causes this worst case (assuming we always pick leftmost item as pivot).
Worst asymptotic performance ¦¨(N2) occurs if array is in sorted order.
[1 2 3 4 5 6 7 8 9 10 … N] [1 2 3 4 5 6 7 8 9 10 … N] [1 2 3 4 5 6 7 8 9 10 … N] …
[1 2 3 4 5 … N/2 … N]
Expected Performance
On average, Quick Select will take ¦¨(N) time. ¡ñ Intuitive picture (not a proof!):
N + N/2 + N/4 + … + 1 = ¦¨(N)
On average, pivot ends up about halfway
~N compares
~N/2 compares ~N/4 compares
Quicksort With Quickselect?
Pivot Selection Strategy
Partition Algorithm
Worst Case Avoidance Strategy
Time to sort 1000 arrays of 10000 ints
Worst Case
Mergesort
N/A
N/A
N/A
2.1 seconds
¦¨(N log N)
Quicksort L3S
Leftmost
3-scan
Shuffle
4.4 seconds
¦¨(N2)
Quicksort LTHS
Leftmost
Tony Hoare
Shuffle
1.7 seconds
¦¨(N2)
Quicksort PickTH
Exact Median
Tony Hoare
Exact Median
10.0 seconds
¦¨(N log N)
Quicksort with PICK to find exact median was terrible. What if we used Quickselect to find the exact median?
¡ñ Resulting algorithm is still quite slow. Also: a little strange to do a bunch of partitions to identify the optimal item to partition around.
Stability, Adaptiveness, Optimization
Sorting Summary (so far)
Listed by mechanism:
¡ñ Selection sort: Find the smallest item and put it at the front.
¡ñ Insertion sort: Figure out where to insert the current item.
¡ñ Merge sort: Merge two sorted halves into one sorted whole.
¡ñ Partition (quick) sort: Partition items around a pivot.
Listed by memory and runtime:
Memory
# Compares
Notes
Heapsort
¦¨(1)
¦¨(N log N) worst
Bad caching (61C)
Insertion
¦¨(1)
¦¨(N2) worst
¦¨(N) if almost sorted
Mergesort
¦¨(N)
¦¨(N log N) worst
Random Quicksort
¦¨(log N) (call stack)
¦¨(N log N) expected
Fastest sort
Other Desirable Sorting Properties: Stability
A sort is said to be stable if order of equivalent items is preserved.
sort(studentRecords, BY_NAME); sort(studentRecords, BY_SECTION);
Bas
3
Fikriyya
4
Jana
3
Jouni
3
Lara
1
Nikolaj
4
Rosella
3
Sigurd
2
Lara
1
Sigurd
2
Bas
3
Jana
3
Jouni
3
Rosella
3
Fikriyya
4
Nikolaj
4
Equivalent items don¡¯t ¡®cross over¡¯ when being stably sorted.
Other Desirable Sorting Properties: Stability
A sort is said to be stable if order of equivalent items is preserved.
sort(studentRecords, BY_NAME); sort(studentRecords, BY_SECTION);
Bas
3
Fikriyya
4
Jana
3
Jouni
3
Lara
1
Nikolaj
4
Rosella
3
Sigurd
2
Lara
1
Sigurd
2
Jouni
3
Rosella
3
Bas
3
Jana
3
Fikriyya
4
Nikolaj
4
Sorting instability can be really annoying! Wanted students listed alphabetically by section.
Sorting Stability
Is insertion sort stable?
www.yellkey.com/reveal
S O R T E X A M P LE
S O R T E X A MP LE O S R TE XA M P L E O R S TE X A M P L E O R S T E X A M PL E E O R S T X A M PL E E O R S T X A M PL E A E O R S T X M PLE A E M OR S T X P LE A E M O P R S T X LE A E L MO P R S T X E A E E L M O P R ST X
(0 swaps)
(1 swap )
(1 swap )
(0 swaps)
(4 swaps)
(0 swaps)
(6 swaps)
(5 swaps)
(4 swaps)
(7 swaps)
(8 swaps)
Is Quicksort stable? ¡ñ Consider ——–>
6
8
3
1
2
7
4
Sorting Stability
Is insertion sort stable? ¡ñ Yes.
¡ñ Equivalent items never move past their equivalent brethren.
Is Quicksort stable?
¡ñ Depends on your partitioning strategy.
Three array partitioning.
S O R T E X A M P LE
S O R T E X A MP LE O S R TE XA M P L E O R S TE X A M P L E O R S T E X A M PL E E O R S T X A M PL E E O R S T X A M PL E A E O R S T X M PLE A E M OR S T X P LE A E M O P R S T X LE A E L MO P R S T X E A E E L M O P R ST X
(0 swaps)
(1 swap )
(1 swap )
(0 swaps)
(4 swaps)
(0 swaps)
(6 swaps)
(5 swaps)
(4 swaps)
(7 swaps)
(8 swaps)
6
7
3
1
2
8
3
Hoare partitioning.
2
3
3
1
6
8
7
3
1
2
3
6
7
8
Stability
Memory
# Compares
Notes
Stable?
Heapsort
¦¨(1)
¦¨(N log N)
Bad caching (61C)
No
Insertion
¦¨(1)
¦¨(N2)
¦¨(N) if almost sorted
Yes
Mergesort
¦¨(N)
¦¨(N log N)
Yes
Quicksort LTHS
¦¨(log N)
¦¨(N log N) expected
Fastest sort
No
This is due to the cost of tracking recursive calls by the computer, and is also an ¡°expected¡± amount. The difference between log N and constant memory is trivial.
You can create a stable Quicksort (i.e. the version from the previous lecture). However, unstable partitioning schemes (like Hoare partitioning) tend to be faster. All reasonable partitioning schemes yield ¦¨(N log N) expected runtime, but with different constants.
Optimizing Sorts
Additional tricks we can play:
¡ñ Switch to insertion sort:
¡ð When a subproblem reaches size 15 or lower, use insertion sort.
¡ñ Make sort adaptive: Exploit existing order in array (Insertion Sort, SmoothSort, TimSort (the sort in Python and Java)).
¡ñ Exploit restrictions on set of keys. If number of keys is some constant, e.g. [3, 4, 1, 2, 4, 3, …, 2, 2, 2, 1, 4, 3, 2, 3], can sort faster (see 3-way quicksort — if you¡¯re curious, see: http://goo.gl/3sYnv3).
¡ñ For Quicksort: Make the algorithm introspective, switching to a different sorting method if recursion goes too deep. Only a problem for deterministic flavors of Quicksort.
Arrays.sort
In Java, Arrays.sort(someArray) uses:
¡ñ Mergesort (specifically the TimSort variant) if someArray consists of Objects.
¡ñ Quicksort if someArray consists of primitives. Why? See A level problems.
Sounds of Sorting (Fun)
Sounds of Sorting Algorithms (of 125 items)
Starts with selection sort: https://www.youtube.com/watch?v=kPRA0W1kECg Insertion sort: https://www.youtube.com/watch?v=kPRA0W1kECg&t=0m9s Quicksort: https://www.youtube.com/watch?v=kPRA0W1kECg&t=0m38s Mergesort: https://www.youtube.com/watch?v=kPRA0W1kECg&t=1m05s Heapsort: https://www.youtube.com/watch?v=kPRA0W1kECg&t=1m28s
LSD sort: https://www.youtube.com/watch?v=kPRA0W1kECg&t=1m54s [coming next Wednesday] MSD sort: https://www.youtube.com/watch?v=kPRA0W1kECg&t=2m10s [coming next Wednesday] Shell¡¯s sort: https://www.youtube.com/watch?v=kPRA0W1kECg&t=3m37s [bonus from last time] Questions to ponder (later… after class):
¡ñ How many items for selection sort?
¡ñ Why does insertion sort take longer / more compares than selection sort?
¡ñ At what time stamp does the first partition complete for Quicksort?
¡ñ Could the size of the input to mergesort be a power of 2?
¡ñ What do the colors mean for heapsort?
¡ñ How many characters are in the alphabet used for the LSD sort problem?
¡ñ How many digits are in the keys used for the LSD sort problem?
Citations
Title image:
http://www.constructionphotography.com/ImageThumbs/A168-02831/3/A168-02831_plastic_bottles_sorted_by _colour_compressed_into_bales_and_ready_for_recycling.jpg
Sorting, Puppies, Cats, and Dogs
A solution to the sorting problem also provides a solution to puppy, cat, dog.
¡ñ Thus: Sorting must be at least as hard as puppy, cat, dog.
¡ñ Because [difficulty of sorting] ¡Ý [difficulty of puppy, cat, dog], any lower
bound on difficulty of puppy, cat, dog must ALSO apply to sorting.
Physics analogy: Climbing a hill with your legs is one way to solve the problem of getting up a hill.
¡ñ Thus: Using ¡°climbing a hill with your legs¡± must be at least as hard as ¡°getting up a hill¡±.
¡ñ Because CAHWYL ¡Ý GUAH, any lower bound on energy to GUAH must also apply to CAHWYL.
¡ñ Example bound: Takes m*g*h energy to climb hill, so using legs to climb the hill takes at least m*g*h energy.