CS61B Lecture #22Today:• Sorting algorithms: why?• Standard methods• Properties of standard methods• SelectionReadings for Today:Data Structures,Chapter 8 (Sorting)Readings for Next Topic: Balanced searches,Data Structures,Chapter 9.Last modified: Mon Oct 29 11:01:37 2001 CS61B: Lecture #22 1Purposes of Sorting• Sorting supports searching• Binary search standard example• Also supports other kinds of search:– Are there two equal items in this set?– Are there two items in this set that both havethe same value for property X?– What are my nearest neighbors?• Used in numerous algorithms, such convex hull (small-est convex polygon enclosing set of points).Last modified: Mon Oct 29 11:01:37 2001 CS61B: Lecture #22 2Some Definitions• A sort is apermutation(re-arrangement) of a se-quence of elements that brings them into order, ac-cording to some complete order.• The ordering may allow unequal items to be equiva-lent– E.g., can be two dictionary definitions for the sameword: if entries sorted only by word, then sortingcould put either entry first.– A sort that does not change the relative order ofequivalent entries is calledstable.•Internal sortskeep all data in primary memory•External sortsprocess large amounts of data in batches,keeping what won’t fit in secondary storage (in theold days, tapes).•Comparison-basedsorting assumes only thing we knowabout keys is order•Radix sortinguses more information about key struc-ture.Last modified: Mon Oct 29 11:01:37 2001 CS61B: Lecture #22 3Sorting by Insertion• Simple idea:– starting with empty sequence of outputs.– add each item from input,insertinginto outputsequence at right point.• Very simple, good for small sets of data.• With vector or linked list, time for find + insert ofone item is at worst Θ(k), where k is # of outputsso far.• So gives us O(N2) algorithm. Can we say more?Last modified: Mon Oct 29 11:01:37 2001 CS61B: Lecture #22 4Inversions• Can run in Θ(N) comparisons if already sorted.• Consider a typical implementation for arrays:for (int i = 1; i < A.length; i += 1) {int j;Object x = A[i];for (j = i-1; j >= 0; j -= 1) {if (A[j].compareTo (x) <= 0) /* (1) */break;A[j+1] = A[j];}A[j+1] = x;}• #times (1) executes ≈ how far x must move.• If all items within K of proper places, then takesO(KN) operations.• Thus good for any amount ofnearly sorteddata.• One measure of unsortedness: # ofinversions:pairsthat are out of order (= 0 when sorted, N(N − 1)/2when reversed).• Each step of j decreases inversions by 1.Last modified: Mon Oct 29 11:01:37 2001 CS61B: Lecture #22 5Shell’s sortIdea: Improve how much improvement we get in eachstep by sortingdistantelements. E.g.:• First sort subsequences of elements 2k− 1 apart,starting at 0, 1, . . . , 2k−2. Each operation can reduce#inversions by as much as 2k+ 1.• Now sort subsequences of elements 2k−1− 1 apart.• End up by doing ordinary insertion sort (elements20= 1 apart), but by then, most inversions gone.• Sort is Θ(N1.5) (take CS170 for why!).#I #C15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 120 -0 14 13 12 11 10 9 8 7 6 5 4 3 2 1 15 105 10 7 6 5 4 3 2 1 14 13 12 11 10 9 8 15 42 90 1 3 2 4 6 5 7 8 10 9 11 13 12 14 15 4 200 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 19Last modified: Mon Oct 29 11:01:37 2001 CS61B: Lecture #22 6Sorting 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 heap.• Gives O(N lg N) algorithm (N remove-first opera-tions).• Since we remove items from end of heap, we can usethat area to accumulate 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: Mon Oct 29 11:01:37 2001 CS61B: Lecture #22 7Merge SortingIdea: Divide data in 2 equal parts; recursively sorthalves; merge results.• Already seen analysis: Θ(N lg N).• Good forexternal sorting:– First break data into small enough chunks to fitin memory and sort.– Then repeatedly merge into bigger and bigger se-quences.– Can merge K sequences ofarbitrary sizeon sec-ondary storage using Θ(K) storage.• For internal sorting, can usebinomial combto or-chestrate:Last modified: Mon Oct 29 11:01:37 2001 CS61B: Lecture #22 8Illustration of Internal Merge Sort• L: (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: Mon Oct 29 11:01:37 2001 CS61B: Lecture #22 9Quicksort: Speed through ProbabilityIdea:•Partitiondata into pieces: everything > apivotvalueat the high end of the sequence to be sorted, andeverything ≤ on the low end.• Repeat recursively on the high and low pieces.• For speed, stop when pieces are “small enough” anddo insertion sort on the whole thing.• Reason: insertion sort has low constant factors. Bydesign, no item will move out of its will move out ofits piece [why?], so when pieces are small, #inver-sions is, too.• Have to choose pivot well. E.g.:medianof first, lastand middle items of sequence.Last modified: Mon Oct 29 11:01:37 2001 CS61B: Lecture #22 10Example of Quicksort• In this example, we continue until pieces are size≤ 4.• Pivots for next step are starred. Arrange to movepivot to dividing line 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: Mon Oct 29 11:01:37 2001 CS61B: Lecture #22 11Performance 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 merge or heap 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 nearlyordered input sets.• Interesting point: randomly shuffling the data before sortingmakes Ω(N2) timeveryunlikely!Last
View Full Document
Unlocking...