CS61B Lecture #25Shell's sortExample of Shell's SortSorting by Selection: HeapsortMerge SortingIllustration of Internal Merge SortQuicksort: Speed through ProbabilityExample of QuicksortPerformance of QuicksortQuick SelectionSelection ExampleSelection PerformanceBetter than N lg N?Beyond Comparison: Distribution CountingDistribution Counting ExampleRadix SortMSD Radix SortPerformance of Radix SortAnd Don't Forget Search TreesSummaryCS61B Lecture #25Today: Sorting, cont.• Standard methods• Properties of standard methods• SelectionReadings for Today:DS(IJ),Chapter 8;Readings for Next Topic: Balanced searches,DS(IJ),Chapter 9;Last modified: Thu Oct 28 16:21:30 2004 CS61B: Lecture #25 1Shell’s sortIdea: Improve insertion sort by first sortingdistantelements:• First sort subsequences of elements 2k− 1 apart:– sort items #0, 2k− 1, 2(2k− 1), 3(2k− 1), . . ., then– sort items #1, 1 + 2k− 1, 1 + 2(2k− 1), 1 + 3(2k− 1), . . ., then– sort items #2, 2 + 2k− 1, 2 + 2(2k− 1), 2 + 3(2k− 1), . . ., then–etc.– sort items #2k− 2, 2(2k− 1) − 1, 3(2k− 1) − 1, . . .,– Each time an item moves, can reduce #inversions by as much as2k+ 1.• Now sort subsequences of elements 2k−1− 1 apart:– sort items #0, 2k−1− 1, 2(2k−1− 1), 3(2k−1− 1), . . ., then– sort items #1, 1 + 2k−1− 1, 1 + 2(2k−1− 1), 1 + 3(2k−1− 1), . . .,–...• End at plain ins ertion sort (20= 1 apart), but with most inversionsgone.• Sort is Θ(N1.5) (take CS170 for why!).Last modified: Thu Oct 28 16:21:30 2004 CS61B: Lecture #25 2Example of Shell’s Sort#I #C15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 120 10 14 13 12 11 10 9 8 7 6 5 4 3 2 1 15 91 100 7 6 5 4 3 2 1 14 13 12 11 10 9 8 15 42 200 1 3 2 4 6 5 7 8 10 9 11 13 12 14 15 4 190 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 -I:Inversions left.C:Comparisons needed to sort subsequences.Last modified: Thu Oct 28 16:21:30 2004 CS61B: Lecture #25 3Sorting by Selection: HeapsortIdea: Keep selecting smallest (or largest) element.• Really bad idea on a simple list or vector.• But we’ve already seen it in action: use he a p.• Gives O(N lg N) algorithm (N remove-first operations).• Since we remove items from end of heap, we can use that area toaccumulate result:19 0 -1 7 23 2 42original:42 23 19 7 0 2 -1heapified:23 7 19 -1 0 2 4219 7 2 -1 0 23 427 0 2 -1 19 23 422 0 -1 7 19 23 420 -1 2 7 19 23 42-1 0 2 7 19 23 42Last modified: Thu Oct 28 16:21:30 2004 CS61B: Lecture #25 4Merge SortingIdea: Divide data in 2 equal parts; recursively sort halves; mer g e re-sults.• Already seen analysis: Θ(N lg N).• Good forexternal sorting:– First break data into small en ough chunks to fit in memory andsort.– Then repeatedly merge into bigger and bigger sequences.– Can merg e K sequences ofarbitrary sizeon secondary storageusing Θ(K) storage.• For internal sorting, can usebinomial combto orchestrate:Last modified: Thu Oct 28 16:21:30 2004 CS61B: Lecture #25 5Illustration of Internal Merge SortL: (9, 15, 5, 3, 0, 6, 10, -1, 2, 20 , 8)00:01:02:03:0 elements processed1 •0: (9)01:02:03:1 element processed00:1 •1: (9, 15)02:03:2 elements processed1 •0: (5)1 •1: (9, 15)02:03:3 elements processed00:01:1 •2: (3, 5, 9, 15)03:4 elements processed00:1 •1: (0, 6)1 •2: (3, 5, 9, 15)03:6 elements processed1 •0: (8)1 •1: (2, 20)02:1 •3: (-1, 0, 3, 5, 6, 9, 10, 15)11 elements processedLast modified: Thu Oct 28 16:21:30 2004 CS61B: Lecture #25 6Quicksort: Speed through ProbabilityIdea:•Partitiondata into piece s: everything > apivotvalue at the highend of the sequence to be sorted, and everythin g ≤ on the low end.• Repeat recursively on the high and low pieces.• For speed, stop when pieces are “small enough” and do insertion sorton the whole thing.• Reason: insertion sort has low constant factors. By design, no itemwill move out of its will move out of its pi ece [why?], so when piecesare small, #inversions is, too.• Have to choose pivot we l l . E.g.:medianof first, last and middleitems of sequence.Last modified: Thu Oct 28 16:21:30 2004 CS61B: Lecture #25 7Example of Quicksort• In this example, we continue until pieces are size ≤ 4.• Pivots for next step are starred. Arrange to move pivot to dividingline each time.• Last step is insertion sort.16 10 13 18 -4 -7 12 -5 19 15 0 22 29 34 -1*-4 -5 -7 -1 18 13 12 10 19 15 0 22 29 34 16*-4 -5 -7 -1 15 13 12* 10 0 16 19* 22 29 34 18-4 -5 -7 -1 10 0 12 15 13 16 18 19 29 34 22• Now everything is “close to” right, so just do insertion sort:-7 -5 -4 -1 0 10 12 13 15 16 18 19 22 29 34Last modified: Thu Oct 28 16:21:30 2004 CS61B: Lecture #25 8Performance of Quicksort• Probabalistic time:– If choice of pivots good, divide data in two each time: Θ(N lg N)with a good constant factor relative to merg e or h eap sort.– If choice of pivots bad, most items on one side each time: Θ(N2).– Ω(N lg N) in best case, so insertion sort better for nearly or-dered input sets.• Interesting point: randomly shuffling the data before sorting makesΩ(N2) timeveryunlikely!Last modified: Thu Oct 28 16:21:30 2004 CS61B: Lecture #25 9Quick SelectionThe Selection Problem: for given k, find kthsmallest element i n data.• Obvious method: sort, select element #k, time Θ(N lg N).• If k ≤ some constant, can easily do in Θ(N ) time:– Go through array, keep smallest k items.• GetprobablyΘ(N)timefor all k by adapting quicksort:– Partition around some pivot, p, as in quicksort, arrange that pivotends up at dividing line.– Suppose that i n the result, pivot is at index m, all elements ≤pivot have indicies ≤ m.– If m = k, you’re done: p is answer.– If m > k, recursively select kthfrom left half of sequence.– If m < k, recursively select (m − k − 1)thfrom right half ofsequence.Last modified: Thu Oct 28 16:21:30 2004 CS61B: Lecture #25 10Selection ExampleProblem: Find just item #10 in the sorted version of arr a y:Initial contents:51 60 21 -4 37 4 49 10 40* 59 0 13 2 39 11 46 310Looking for #10 to left of pivot 40:13 31 21 -4 37 4* 11 10 39 2 0 40 59 51 49 46 600Looking for #6 to right of pivot 4:-4 0 2 4 37 13 11 10 39 21 31* 40 59 51 49 46 604Looking for #1 to right of pivot 31:-4 0 2 4 21 13 11 10 31 39 37 40 59 51 49 46 609Just two elements; just sort and return # 1:-4 0 2 4 21 13 11 10 31 37 39 40 59 51 49 46 609Result: 39Last modified: Thu Oct 28 16:21:30 2004 CS61B: Lecture #25 11Selection Performance• For this algorithm,
View Full Document
Unlocking...