CSC152 2006S, Class 49: Faster Sorts
Admin:
* Office hour signup outside office
* Are there questions on Exam 3?
* In an attempt at supporting today's protest, I will only hold half a class today.
Overview:
* Divide-and-Conquer Sorting.
* Merge Sort.
* Iterative Merge Sort.
* Asymptotic Analysis of Merge Sort.
* Quicksort.
More Efficient Sorts
* Sort more efficiently by "divide and conquer"
* Two ways to divide:
* First half vs. second half "Merge sort"
* Smaller vs. larger C.A.R. Hoare "Quicksort"
* Vector [23, 5, 1, 22, 0, 50, 18, 10]
* Divide into two halves
* First half [23, 5, 1, 22]
* Second half [0, 50, 18, 10]
* Sort the halves
* F: [1,5,22,23]
* S: [0,10,18,50]
* Put them back together (Merge)
* Take the smaller first element of either half
* Result: [0, ...]
* Lop off that element
* F: [1,5,22,23]
* S: [10,18,50]
* Do it again
* Result: [0, 1, ....]
* F: [5,22,23]
* S: [10,18,50]
* Do it again
* Result: [0, 1, 5, ....]
* F: [22,23]
* S: [10,18,50]
* ...
* When you run out of stuff in one part, shove the other part at the end
* When we sort the halves, do it recursively
* Base case: Empty: Sorted. // May not be necessary
* Base case: One element: Sorted.
* Running time? [See figure]
O(nlogn)
* Beats the O(n^2) for Friday's
* Equal to Heapsort
* Is this sorting algorithm stable? Can we make it stable?
* Stable: Equal elements preserve order
* If when we're merging, we take from the left half when confronted with equal elements, it's stable
You can do a more formal analysis in combinatorics, using recurrence relations
t(n) = n + 2*t(n/2)
t(n) = n + 2*(n/2 + 2*t(n/4))
t(n) = n + n + 4*t(n/4)
...
Other way to divide and conquer: By size (small and large)
* Vector [23, 5, 1, 22, 0, 50, 18, 10]
* Small:
* Large for this list: 23, 22
* Small for this list: 5, 1
* new list:
* Large:
* Small: -1, -1000
* But what if the rest are all < -1000
* Need some context for determining large and small
* Find largest O(n)
* Find smallest O(n)
* Average O(1)
* Things smaller than average are small, things larger than average are larege
* Try 1, 2, 4, 8, 16, 32, 4, 128, 256, 512
* Hoare's great idea: Guess the median, most of the time you're close
* Chance is your friend
* Empirical data support his claim
* Two key ideas in Quicksort
* Divide-and-conquer
* Chance is your friend
* Merging is easy in Quicksort: Concatenate
* Phrased as divde-and-conquer
* Pick a pivot
* Split into small and large
* Sort two halves
* Concatenate
Sam Rebelsky never logs out and [athanasa] doesn't have any lame ideas. Sad...