碩士算法2010_第4章_排序算法001

1、1算法設(shè)計與分析李洪偉李洪偉 博士博士電子科技大學計算機科學與工程學院電子科技大學計算機科學與工程學院http:/ 排序算法排序算法l基于相鄰元素的比較排序算法1 插入排序法2 冒泡排序法3 選擇排序法l基于分治法策略的排序算法1 融合（歸并）排序法2 快速排序法3 Shell排序法l堆排序1 堆的性質(zhì)2 堆排序算法3 加速堆排序l基于比較的排序算法復(fù)雜度下界l基數(shù)排序3排序的應(yīng)用排序的應(yīng)用nSearching on unsorted data by comparing keys, optimal solutions require (n) comparisons.nSearching on

2、sorted data by comparing keys, optimal solutions require (log n) comparisons.nSorting data for usersnMore4排序問題排序問題n排序就是把一個無序集合中的元素按照一定順序排列成線性結(jié)構(gòu)。n例：將電話簿或字典的條目按字母表的順序排列起來以便更有利于查找。n內(nèi)部排序內(nèi)部排序（internal sort）：所有的數(shù)據(jù)都存儲在計算機的高速隨機存取存儲器中，數(shù)據(jù)的讀取時間可以忽略不計。n外部排序外部排序（external sort）：對低速外存設(shè)備中存放的數(shù)據(jù)進行排序。 5Insertion Sortn

3、Strategy: nInsertion of an element in proper order:nBegin with a sequence E of n elements in arbitrary ordernInitially assume the sorted segment contains the first elementnLet x be the next element to be inserted in sorted segment, pull x “out of the way”, leaving a vacancynrepeatedly compare x to t

4、he element just to the left of the vacancy, and as long as x is smaller, move that element into the vacancy, nelse put x in the vacancy,nrepeat the next element that has not yet examined.6i=0 1 2 3 4 5 6 742 20 17 13 13 13 13 1320 42 20 17 17 14 14 1417 17 42 20 20 17 17 1513 13 13 42 28 20 20 1728

5、28 28 28 42 28 23 2014 14 14 14 14 42 28 2323 23 23 23 23 23 42 2815 15 15 15 15 15 15 42Insertion Sort: e.g.7Insertion Sort: AlgorithmnInputE, an array of elements, and n =0, the number of elements. The range of indexes is 0, , n-1nOutputE, with elements in nondecreasing order of their keysnvoid in

6、sertionSort(Element E, int n)int xindex;for (xindex = 1; xindex n; xindex+)Element current = Exindex;key x = current.keyint xLoc = shiftVacRec(E, xindex, x);ExLoc = current;return;8Specification for subroutinenSpecificationnint shiftVacRec(Element E, int vacant, Key x)nPreconditionnVacant is nonnega

7、tivenPostconditionsn1. Elements in E at indexes less than xLoc are in their original positions and have keys less than or equal to xn2. Elements in E at positions xLoc+1, , vacant are greater than x and were shifted up by one position from their positions when shiftVacRec was invoked.9Algorithm shif

8、tVacRecnint shiftVacRec(Element E, int vacant, Key x)int xLoc;if (vacant = 0)xLoc = vacant;else if (Evacant-1.key = x)xLoc = vacant;elseEvacant = Evacant-1;xLoc = shiftVacRec(E, vacant-1, x);return xLoc10Insertion Sort: AnalysisnWorst-Case ComplexityW(n) = i=1 to n-1i = n(n-1)/2 (n2)nAverage Behavio

9、raverage number of comparisons in shiftVacRec1/(i+1) i=1 to j (j) + i/(i+1) = i/2+1-1/(i+1)A(n) = i=1 to n-1 i/2+1-1/(i+1) (n2)/411Insertion Sort: OptimalitynTheorem 4.1nAny algorithm that sorts by comparison of keys and removes at most one inversion after each comparison must do at least n(n-1)/2 c

10、omparisons in the worst case and at least n(n-1)/4 comparisons on the average (for n elements)nProofnInsertion Sort is optimal for algorithms that works “l(fā)ocally” by interchanging only adjacent elements. nBut, it is not the best sorting algorithm. 1213Algorithm BubbleSortVoid Bubsort(ELEM* aray, int

11、 n) for(int i=0; i n-1; i+) / Bubble ith record for(int j=n-1; j i; j-)if (key(arrayj) 0 need more comparisonwhile flag 0k = k 1flag = 0for i = 1 to k do beginif L i L i+1 thenbeginswap(Li, Li+1) flag = 1 end end forBubble Sort (2)16i=0 1 2 3 4 5 6 742 20 17 13 13 13 13 1320 17 13 17 14 14 14 1417 1

12、3 20 14 17 15 15 1513 28 14 20 15 17 17 1728 14 23 15 20 20 20 2014 23 15 23 23 23 23 2323 15 28 28 28 28 28 2815 42 42 42 42 42 42 42Bubble Sort (2)17flag = n ; / flag 0 need more comparisonwhile flag 0 k = flag - 1;flag = 0for i = 0 to k doif L i L i+1 thenbeginswap(Li, Li+1) flag = i ;endend forB

13、ubble Sort (3)18i=0 1 2 3 4 42 14 14 13 1314 17 13 14 1417 13 17 17 1713 22 20 20 2022 20 22 22 2220 23 23 23 2323 24 24 24 2424 42 42 42 42Bubble Sort (3)19Void Selsort(ELEM* aray, int n) for(int i=0; ii; j-) /Find the least if (key(arrayj)key(arraylowindex)lowindex = j;swap(arrayj,arraylowindex);

14、Selection Sort20i=0 1 2 3 4 5 6 742 13 13 13 13 13 13 1320 20 14 14 14 14 14 1417 17 17 15 15 15 15 1513 42 42 42 17 17 17 1728 28 28 28 28 20 20 2014 14 20 20 20 28 23 2323 23 23 23 23 23 28 2815 15 15 17 42 42 42 42Selection Sort21Comparisons: Insertion Bubble SelectionBest Case(n)(n)(n)Average Ca

15、se(n)(n)(n)Worst Case(n)(n)(n)Swaps : . Best Case0 0 (n)Average Case(n)(n) (n)Worst Case(n)(n) (n)All of these sorts rely on exchanges of adjacent records.Exchange Sort SummaryDivide and ConquernIt is often easier to solve several small instances of a problem than a large one.ndivide the problem int

16、o smaller instances of the same problemnsolve (conquer) the smaller instances recursivelyncombine the solutions to obtain the solution for original inputnSolve(I)n = size(I)if (n = smallsize)solution = directlySolve(I);elsedivide I into I1, , Ik.for each i in 1, , kSi = solve(Ii);solution = combine(

17、S1, , Sk);return solution;23MergesortnStrategyAlgorithm: MergesortnInput: Array E and indexes first, and Last, such that the elements Ei are defined for first = i = last.nOutput: Efirst, , Elast is sorted rearrangement of the same elementsnvoid mergeSort(Element E, int first, int last)if (first last

18、)int mid = (first+last)/2;mergeSort(E, first, mid);mergeSort(E, mid+1, last);merge(E, first, mid, last);return;25Merging Sorted SequencesnProblem: nGiven two sequences A and B sorted in nondecreasing order, merge them to create one sorted sequence CnStrategy: ndetermine the first item in C: It is th

19、e minimum between the first items of A and B. Suppose it is the first items of A. Then, rest of C consisting of merging rest of A with B.26Algorithm: MergenMerge(A, B, C)if (A is empty)rest of C = rest of Belse if (B is empty)rest of C = rest of Aelse if (first of A 1) qsort(array, i, k-1);/Sort lef

20、tif(j-k) 1) qsort(array, k+1,j);/Sort right int findpivot(ELEM* array, int i, int j) return(i+j)/2;Quicksort29Final Sorted ArrayPivot=60Pivot=5Pivot=85Pivot=42Pivot=88Pivot=57Pivot=73Pivot=6 72 6 57 88 60 42 83 73 48 8548 6 57 42 60 88 83 73 72 85 6 42 57 4872 73 85 88 836 42 48 57 60 72 73 83 85 88

21、42 48 5785 83 8842 4883 85Quicksort Example30 int partition(ELEM* array,int l, int r, KEY pivot) do/move the bounds inward until they meet while( key(array+l) pivot);/move left swap(arrayl,arrayr); /swap out-of-place vals while (l2; i/=2) / For each incrementfor(int j=0; ji; j+) /Sort each sublistin

22、ssort2(&arrayj, n-j, i) inssort2(array, n, 1);/Version of Insertion Sort for varying incrementsvoid inssort2(ELEM* A, int n, int incr)for(int i=incr; i=incr)&(key(Aj= 1; i-)curMax = getMax(H)deleteMax(H);Ei = curMax;ndeleteMax(H) / Outlinecopy the rightmost element of the lowest level of H i

23、nto Kdelete the rightmost element on the lowest level of HfixHeap(H, K);Fixheap OutlinenfixHeap(H, K) / Outlineif (H is a leaf)insert K in root(H);elseset largerSubHeap to leftSubtree(H) or rightSubtree(H), whichever has larger key at is root. This involves one key comparison. if (K.key = root(large

24、rSubHeap.key)insert K in root(H);elseinsert root(largerSubHeap) in root(H);fixHeap(largerSubHeap, K);return;nFixHeap requires 2h comparisons of keys in the worst case on a heap with height h. W(n) 2 lg(n)44Heap construction Strategy nbase case is a tree consisting of one nodeConstruct Heap: OutlineI

25、nput: A heap structure H that does not necessarily have the partial order tree propertyOutput: H with the same nodes rearranged to satisfy the partial order tree propertynvoid constructHeap(H) / Outlineif (H is not a leaf)constructHeap (left subtree of H);constructHeap (right subtree of H);Element K

26、 = root(H);fixHeap(H, K);return;nT(n) = T(n-r-1) + T(r) + 2 lg(n) for n 1nT(n) O(n); heap is constructed in linear time. 46Heapsort AnalysisnThe number of comparisons done by fixHeap on heap with k nodes is at most 2 lg(k)so the total for all deletions is at most2 k=1 to n-1( lg(k) ) (2n lg(n)nTheor

27、em: The number of comparisons of keys done by Heapsort in the worst case is 2n lg(n) + O(n).nHeapsort does (2n lg(n) comparisons on average as well. (How do we know this?)47Accelerated HeapsortnSpeed up Heapsort by about a factor of two.nNormal fixHeap costs 2h comparisons in the worst case. Can we

28、do better?nThe solution is a surprising application of divide and conquer!filter the vacant position halfway down the tree, h/2test whether K is bigger than the parent of vacantyes: bubble the vacant back up to where K should beno: repeat filter the vacant position another halfway down recursively!4

29、8Accelerated Heapsort in ActionnK = 55nnodes not all shown49Action continuesnK = 55Accelerated Heapsort Algorithmvoid fixHeapFast(Element E, int n, Element K, int vacant, int h)if (h = 1) Process heap of height 0 or 1elseint hStop = h/2int vacStop = promoste (E, hStop, vacant, h);/ vacStop is new va

30、cnt location, at height hStopint vacParent = vacStop / 2; if (EvacParent.key = K.key)EvacStop = EvacParent;bubbleUpHeap (E, vacant, K, vacParent);elsefixHeapFast (E, n, K, vacStop, hStop);51Algorithm: promoteint promote (Element E, int hStop, int vacant, int h)int vacStop;if (h = hStop)vacStop = vac

31、ant;else if (E2*vacant.key = E2*vacant+1.key)Evacant = E2*vacant+1;vacStop = promote (E, hStop, 2*vacant+1, h-1)elseEvacant = E2*vacant;vacStop = promote (E, hStop, 2*vacant, h-1);return vacStop;Algorithm: bubbleUpHeapvoid bubbleUpHeap (Element E, int root, Element K, int vacant)if (vacant = root)Ev

32、acant = K;elseint parent = vacant / 2;if (K.key = Eparent.key)Evacant = K;elseEvacant = Eparent;bubbleUpHeap (E, root, K, parent);53Analysis: fixHeapFastnEssentially, there is one comparison each time vacant changes a level due to the action of either bubbleUpHeap or Promote. The total is h.nAssume

33、bubbleUpHeap is never call, so fixHeapFast reaches its base case. Then, it requires lg(h) checks along the way to see whether it needs to reverse direction.nTherefore, altogether fixHeapFast uses h+lg(h) comparisons in the worst case. 54Accelerated Heapsort AnalysisnThe number of comparisons done by

34、 fixHeapFast on heap with k nodes is at most lg(k)so the total for all deletions is at most k=1 to n-1( lg(k) ) (n lg(n)nTheorem: The number of comparisons of keys done by Accelerated Heapsort in the worst case is n lg(n) + O(n).55Comparison of Sorting AlgorithmsAlgorithmWorst caseAverageSpace Usage

35、Insertion n2/2(n2)in placeQuicksort n2/2(n log n)log nMergesort n lg n(n log n)nHeapsort 2n lg n(n log n)in placeAc.Heaps. n lg n(n log n)in placenAccelerated Heapsort currently is the method of choice.56Exchange Sorting Lower BoundnTry to prove a lower bound for all possible sorting algorithmsnNow

36、prove (n log n) is the lower boundnComparison based sorting can be modeled by a binary tree that must have (n!) leaves.nThere are n! permutations, and at least 1 node for each permutation.Lower Bounds for Sorting by Comparison of KeysnThe Best possible!nLower Bound for Worst CasenLower Bound for Ave

37、rage BehaviornUse decision tree for analyzing the class of sorting algorithms (by comparison of keys)nAssuming the keys in the array to be sorted are distinct.nEach internal node associates with one comparison for keys xi and xj; labeled i :jnEach leaf nodes associates with one permutation (total n!

38、 permutations for problem size n)nThe action of Sort on a particular input corresponds to following one path in its decision tree from the root to a leaf.58Decision tree for sorting algorithmsnn = 359Decision TreesnThe tree must be log n! levels deep.nBy Stirling formula ：log n! = O(n log n)nThere a

39、re n! permutations, and at least 1 node for each permutation.60Lower Bound for Worst CasenLemma: nLet L be the number of leaves in a binary tree and let h be its height. nThen L = Ceiling lg L nFor a given n, L = n!, the decision tree for any algorithm that sorts by comparison of keys has height as

40、least Ceiling lg n! .nTheorem: nAny algorithm to sort n items by comparisons of keys must do at least Ceiling lg n! , nor approximately Ceiling n lg n 1.443 n , nkey comparisons in the worst case. 61Lower Bound for Average BehaviornTheorem: nThe average number of comparisons done by an algorithm to

41、sort n items by comparison of keys is at least lg n! nor approximately n lg n 1.443 n nThe only difference from the worst-case lower bound is that there is no rounding up to an integernthe average needs not be an integer, nbut the worst case must be.62Improvement beyond lower bound?Know more Do bett

42、ernUp to now, nonly one assumption was make about the keys: They are elements of linearly ordered set.nThe basic operation of the algorithms is a comparison of two keys.nIf we know more (or make more assumptions) about the keys,nwe can consider algorithms that perform other operations on them.n/ Rec

43、all algorithms for searching from unordered data vs. searching from ordered dataUsing properties of the keysnsupport the keys are namesnsupport the keys are all five-digit decimal integersnsupport the keys are integer between 1 and 10. nFor sorting each of these examples, the keys arendistributed in

44、to different piles as a result of examining individual letters or digits in a key or comparing keys to predetermined valuesnsort each pile individuallyncombine all sorted pilesnAlgorithms that sort by such methods are not in the class of algorithms previously considered becausento use them we must k

45、now something about either the structure or the range of the keys.64Radix SortnAssume that the sorting data are positive integers, radix sort will distribute the numbers into 10 boxes according to the first digit, then collect the numbers in the way that keeps the order from the 10 boxes. nAgain distribute the numbers into 10 boxes according to the second digit, collect them in order, and so on, until the highest digit has been treated.65Radix SortnStrategy: It is startling thatnif the keys ar