数据结构英文教学课件：chapter9 Sorting

1、SortingCHAPTER 9Sorting2Motivation Why Sorting Why efficient sorting methods are so important Sequential search, O(n) Binary search, O(logn) Terms explanation list: fit in memory file: store at external devices record: information for an object field: each record can be broke into smaller unit key:

2、the field to be examine3Introduction Given a set (container) of n elements E.g. array, set of words, etc. Suppose there is an order relation that can be set across the elements Goal Arrange the elements in ascending order (or descending order) Start 1 23 2 56 9 8 10 100 End 1 2 8 9 10 23 56 1004Sort

3、ing Problem Definition given (R0, R1, , Rn-1), where Ri = key + data find a permutation , such that K(i-1) K(i), 0in-1 sorted K(i-1) K(i), 0in-15按照成绩排序按照成绩排序6Sorting Problem stable if i j and Ki = Kj then Ri precedes Rj in the sorted list internal sort vs. external sort criteria # of key comparisons

4、 # of data movements7次关键字排序的结果次关键字排序的结果8SelectionsortThe family of sorting methodsMain sorting themesComparison-basedsortingTranspositionsortingBubbleSortInsert andkeep sortedDivide andconquerInsertionsortTreesortHeapsortQuickSort MergeSortProxmapSortRadixSortShellSortDiminishingincrementsortingAddr

5、ess-basedsortingPriority queuesorting9sorting algorithms types of comparison-based sorting algorithm Insertion Sorting insert and keep sorted Shell sort diminishing increment sorting transposition sorting Bubble sort and Quick sort Selection sort priority queue sorting Merge sort divide and conquer

6、sorting10#ifndef DATALIST_H#define DATALIST_H#include const int DefaultSize = 100;template class datalist template class Element private: Type key;/关键码关键码 field otherdata;/其它数据成员其它数据成员public: Element ( ) : key(0), otherdata(NULL) Class definition of sorting list11 Type getKey ( ) return key; /提取关键码提

7、取关键码 void setKey ( const Type x ) key = x; /修改修改 Element & operator = /赋值赋值 ( Element & x ) this = x; int operator = ( Type & x ) /判判this = x return ! ( this x | x this ); int operator != ( Type & x ) /判判this != x return this x | x this; int operator x ); int operator = ( Type &

8、x ) /判判this x return ! ( this x ); int operator ( Type & x ) /判判this x; 12template class datalist public: datalist ( int MaxSz = DefaultSize ) : /构造函数构造函数 MaxSize ( Maxsz ), CurrentSize (0) Vector = new Element MaxSz; void swap ( Element & x, /对换对换 Element & y ) Element temp = x; x = y;

9、y = temp; private: Element * Vector; /存储向量存储向量 int MaxSize, CurrentSize; /最大与当前个数最大与当前个数13Insertion Sorting- Always insert in the correct position-Simple inserting,BST An example is using a Binary Search Tree which gives the TreeSort An in-order traversal visits each element in the tree in ascending

10、 order O(n log n) because log n to find insertion place multiplied by the number of elements to be inserted1415template void InsertionSort ( datalist & list ) /按关键码 Key 非递减顺序对表进行排序 for ( int i = 2; i list.CurrentSize; i+ ) Insert ( list, i );Insertion Sorting Algorithm16template viod Insert ( da

11、talist & list, int i ) list.Vector0 = list.Vectori; /sentinel int j = i; /从后向前顺序比较从后向前顺序比较 while ( list.Vector0.getKey ( ) binary search reduce # of comparisons, # of moves unchanged List insertion sort array - linked list sequential search, move - 0192021Shell sort diminishing increment sorting

12、 Named after D.L. Shell! But it is also rather like shrinking shells of sorting, for Insertion Sort. Shell sort aims to reduce the work done by insertion sort (i.e. scanning a list and inserting into the right position). It can be shown that this approach will sort a list with a time complexity of O

13、(N1.25).22Shell sort diminishing increment sorting Do the following: Begin by looking at the lists of elements x1 elements apart and sort those elements by insertion sort Reduce the number x1 to x2 so that x1 is not a multiple of x2 and repeat these two steps until x2 = 1.2324 25template void Shells

14、ort ( datalist & list ) int gap = list.CurrentSize / 2; / gap 是子序列间隔是子序列间隔 while ( gap ) /循环循环,直到直到gap为零为零 ShellInsert ( list, gap ); /一趟直接插入排序一趟直接插入排序gap = gap = 2 ? 1 : ( int ) ( gap/2.2 ); /修改修改 Shell Sorting Algorithm26template voidshellInsert ( datalist & list; const int gep ) /一趟希尔排序一趟

15、希尔排序,按间隔按间隔gap划分子序列划分子序列 for ( int i = gap; i list.CurrentSize; i+) Element temp = list.Vectori;int j = i;while ( j = gap & temp.getKey ( ) E2 then Swap(E1, E2) and set flag = true 3. If flag = true goto 1. What happens?29Bubble Sort11 23 2 56 9 8 10 10021 2 23 56 9 8 10 10031 2 23 9 56 8 10 100

16、41 2 23 9 8 56 10 10051 2 23 9 8 10 56 100- finish the first traversal - start again -11 2 23 9 8 10 56 10021 2 9 23 8 10 56 10031 2 9 8 23 10 56 10041 2 9 8 10 23 56 100- finish the second traversal - start again -.Why Bubble Sort ?30template void BubbleSort (datalist & list ) int pass = 1; int

17、 exchange = 1; while ( pass list.CurrentSize & exchange ) BubbleExchange ( list, pass, exchange ); pass+; Algorithm of Bubble Sort(1)31template void BubbleExchange ( datalist & list , const int i, int & exchange ) exchange = 0; /交换标志置为交换标志置为0,假定未交换假定未交换 for ( int j = 0;j list.Vectorj+1.g

18、etKey ( ) ) /逆序逆序 Swap ( list.Vectorj, list.Vectorj+1 ); /交换交换 exchange = 1; /交换标志置为交换标志置为1,有交换有交换 Algorithm of Bubble Sort(2)32Running Time for Bubble Sort One traversal = move the maximum element to the end Traversal #i : n i + 1 operations Running time:(n 1) + (n 2) + + 1 = (n 1) n / 2 = O(n 2) W

19、hen does the worst case occur ? Best case ?33QuickSort As its name implies, QuickSort is the fastest known sorting algorithm in practice (address-based sorts can be faster) It was devised by C.A.R. Hoare in 1962 Its average running time is O(n log n) and it is very fast It has worst-case performance

20、 of O(n2) but this can be made very unlikely with little effort34QuickSort The idea is as follows:1. If the number of elements to be sorted is 0 or 1, then return2. Pick any element, v (this is called the pivot)3. Partition the other elements into two disjoint sets, S1 of elements v, and S2 of eleme

21、nts v4. Return QuickSort (S1) followed by v followed by QuickSort (S2)35QuickSort example514210 3915 12Pick the middle element as the pivot, i.e., 1051423915 12Partition into the two subsets belowSort the subsets12345912 15Recombine with the pivot12345910 12 1536Partitioning example51142510391512Pic

22、k the middle element as the pivot, i.e., 10Move the pivot out of the way by swapping it with the first element10114255391512swapPosStep along the array, swapping small elements into swapPos10411255391512swapPos37Partitioning example (2)10452511391512swapPos10453112591512swapPos10453925111512swapPos3

23、8Pseudo code for partitioningpivotPos = middle of array a;swap apivotPos with afirst; / Move the pivot out of the wayswapPos = first + 1;for each element in the array from swapPos to last do: / If the current element is smaller than pivot we / move it towards start of array if (acurrentElement afirs

24、t): swap aswapPos with acurrentElement; increment swapPos by 1;39Pseudo code for partitioning/ Now move the pivot back to its rightful placeswap afirst with aswapPos-1;return swapPos-1; / Pivot position40template void QuickSort ( datalist &list, const int left, const int right ) /在待排序区间在待排序区间 le

25、ft right 中递归地进行快速排序中递归地进行快速排序 if ( left right) int pivotpos = Partition ( list, left, right ); /划分划分 QuickSort ( list, left, pivotpos-1); /在左子区间递归进行快速排序在左子区间递归进行快速排序 QuickSort ( list, pivotpos+1, right ); /在左子区间递归进行快速排序在左子区间递归进行快速排序 Algorithm for Quick Sorting41template int Partition ( datalist &

26、;list, const int low, const int high ) int pivotpos = low; /基准位置基准位置Swap(List.Vectorlow,List.Vextor(low+high)/2);Element pivot = list.Vectorlow; for ( int i = low+1; i = high; i+ ) if ( list.Vectori.getKey ( ) pivot.getKey( ) & +pivotpos != i ) Swap ( list.Vectorpivotpos, list.Vectori ); /小于基准对象

27、的交换到区间的左侧去小于基准对象的交换到区间的左侧去 Swap ( list.Vectorlow, list.Vectorpivotpos ); return pivotpos;42Analysis of QuickSort We assume a random choice of pivot Let the time to carry out a QuickSort on n elements be T(n) We have T(0) = T(1) = 1 The running time of QuickSort is the running time of the partitionin

28、g (linear in n) plus the running time of the two recursive calls of QuickSort Let i be the number of elements in the left partition, then T(n) = T(i) + T(ni1) + cn (for some constant c)43Worst-case analysis If the pivot is always the smallest element, then i = 0 always We ignore the term T(0) = 1, s

29、o the recurrence relation isT(n) = T(n1) + cn So, T(n1) = T(n2) + c(n1) and so on until we getT(2) = T(1) + c(2)44Worst-case analysis Substituting back up gives T(n) = T(1) + c(n + + 2) = O(n2) Notice that this case happens if we always take the pivot to be the first element in the array and the arr

30、ay is already sorted So, in this extreme case, QuickSort takes O(n2) time to do absolutely nothing!45Best-case analysis In the best case, the pivot is in the middle To simplify the equations, we assume that the two subarrays are each exactly half the length of the original (a slight overestimate whi

31、ch is acceptable for big-Oh calculations) So, we get T(n) = 2T(n/2) + cn This is very similar to the formula for MergeSort, and a similar analysis leads to T(n) = cn log2n + n = O(n log n)46Average-case analysis We assume that each of the sizes of the left partition are equally likely, and hence hav

32、e probability 1/n With this assumption, the average value of T(i), and hence also of T(ni1), is (T(0) + T(1) + + T(n1)/n Hence, our recurrence relation becomesT(n) = 2(T(0) + T(1) + + T(n1)/n + cn47Average-case analysis(2) Multiplying by n givesnT(n) = 2(T(0) + T(1) + + T(n1) + cn2 Replacing n by n1

33、 gives(n1)T(n1) = 2(T(0) + T(1) + + T(n2) + c(n1)2 Subtracting the last equation from the previous one givesnT(n) (n1)T(n1) = 2T(n1) + 2cn c48Average-case analysis (3) Rearranging, and dropping the insignificant c on the end, gives nT(n) = (n+1)T(n1) + 2cn Divide through by n(n+1) to getT(n)/(n+1) =

34、 T(n1)/n + 2c/(n+1) Hence, T(n1)/n = T(n2)/(n1) + 2c/n and so on down toT(2)/3 = T(1)/2 + 2c/349Average-case analysis (4) Substituting back up givesT(n)/(n+1) = T(1)/2 + 2c(1/3 + 1/4 + + 1/(n+1) The sum in brackets is about loge(n+1) + 3/2, where is Eulers constant, which is approximately 0.577 So,

35、T(n)/(n+1) = O(log n) and T(n) = O(n log n)50Selection Sorting Simple Selection Sorting Priority Queue Implementation51Simple Selection sort Given an array of length n, Search elements 0 through n-1 and select the smallest,Swap it with the element in location 0 Search elements 1 through n-1 and sele

36、ct the smallest,Swap it with the element in location 1 Search elements 2 through n-1 and select the smallest,Swap it with the element in location 2 . Continue in this fashion until theres nothing left to search5253Example and analysis of selection sort The selection sort might swap an array element

37、with itself-this is harmless, and not worth checking for Analysis: The outer loop executes n-1 times The inner loop executes about n/2 times on average (from n to 2 times) Work done in the inner loop is constant (swap two array elements) Time required is roughly (n-1)*(n/2) You should recognize this

38、 as O(n2)54template void SelectSort ( datalist & list ) for ( int i = 0; i list.CurrentSize-1; i+ ) SelectExchange ( list, i );Algorithm for Simple Selection Sorting55template void SelectExchange ( datalist & list, const int i ) int k = i; for ( int j = i+1; j list.CurrentSize; j+) if ( list

39、.Vectorj.getKey ( ) list.Vectork.getKey ( ) ) k = j; /当前具最小关键码的对象当前具最小关键码的对象 if ( k != i ) /对换到第对换到第 i 个位置个位置 Swap ( list.Vectori, list.Vectork );56Heap: array implementation12489105376Is it a good idea to store arbitrary binary trees as arrays? May have many empty spaces!57Array implementationThe r

40、oot node is A1.The left child of Aj is A2jThe right child of Aj is A2j + 1The parent of Aj is Aj/2 (note: integer divide)1256431 2 5 4 3 6Need to estimate the maximum size of the heap.58Heapsort(1) Build a binary heap of N elements the minimum element is at the top of the heap(2) Perform N DeleteMin

41、 operations the elements are extracted in sorted order(3) Record these elements in a second array and then copy the array back59Heapsort running time analysis(1) Build a binary heap of N elements repeatedly insert N elements O(N log N) time (there is a more efficient way)(2) Perform N DeleteMin oper

42、ations Each DeleteMin operation takes O(log N) O(N log N)(3) Record these elements in a second array and then copy the array back O(N) Total: O(N log N) Uses an extra array60Heapsort: no extra storage After each deleteMin, the size of heap shrinks by 1 We can use the last cell just freed up to store

43、 the element that was just deleted after the last deleteMin, the array will contain the elements in decreasing sorted order To sort the elements in the decreasing order, use a min heap To sort the elements in the increasing order, use a max heap the parent has a larger element than the child61Heapso

44、rtSort in increasing order: use max heapDelete 9762Heapsort: A complete example前前7 7个关键字个关键字重新建堆重新建堆63Example (contd)前前5 5个关键字个关键字重新建堆重新建堆64Example (contd)数组中的排列方式数组中的排列方式65Overview (comparison-based sorting) Divide and Conquer sorting We repeatedly divide the set of n elements into two partitions T

45、his reduces the number of comparisons required during sorting significantly66Overview (comparison-based sorting) We either do: a bit of sorting as we partition, ending up with a completely sorted array when no further partitioning can be done (QuickSort), or we do a bit of sorting as we merge the pa

46、rtitions, leading to a completely sorted array when all the partitions have been fully merged (MergeSort) Average time complexity is O(n log n), worst case is O(n2)67Divide and conquer sortingMergeSortQuickSort68and conquer1234591015124539101551421039151524310915MergeSort69MergeSort For MergeSort an

47、 initial array is repeatedly divided into halves (usually each is a separate array), until arrays of just one element remain At each level of recombination, two sorted arrays are merged into one This is done by copying the smaller of the two elements from the sorted arrays into the new array, and th

48、en moving along the arrays11324262152738AptrBptrCptr70Merging113242621527381AptrBptrCptr1132426215273812AptrBptrCptr113242621527381213AptrBptrCptretc.71template void merge ( datalist & initList, datalist & mergedList, const int l, const int m, const int n ) int i = l, j = m+1, k = l; while (

49、 i = m & j = n ) /两两比较两两比较 if ( initList.Vectori.getKey ( ) = initList.Vectorj.getKey ( ) ) mergedList.Vectork = initList.Vectori; i+; k+; else mnlm+172 mergedList.Vectork = initList.Vectorj; j+; k+; if ( i = m ) for ( int n1 = k, n2 = i; n1 = n & n2 = m; n1+, n2+ ) mergedList.Vectorn1 = ini

50、tList.Vectorn2; else for ( int n1 = k, n2 = j; n1 = n & n2 = n; n1+, n2+) mergedList.Vectorn1 = initList.Vectorn2;73template void MergePass ( datalist & initList, datalist & mergedList, const int len ) int i =0; while ( i+2*len = initList.CurrentSize ) merge ( initList, mergedList, i, i+len-1, i+2*len-1); i += 2 * len; if ( i+len = initList.CurrentSize-1 ) merge ( initList, mergedList, i, i+len-1, initList.CurrentSize-1 ); else