《【精品数据结构】Sorting.ppt》由会员分享，可在线阅读，更多相关《【精品数据结构】Sorting.ppt（35页珍藏版）》请在三一文库上搜索。
1、Sorting,Each record contains a field called the key. Linear order: comparison. Measures of cost: Comparisons Swaps,Insertion Sort (1),Insertion Sort (2),template void inssort(Elem A, int n) for (int i=1; i0) Best Case: Worst Case: Average Case:,Bubble Sort (1),Bubble Sort (2),template void bubsort(E
2、lem A, int n) for (int i=0; ii; j-) if (Comp:lt(Aj, Aj-1) swap(A, j, j-1); Best Case: Worst Case: Average Case:,Selection Sort (1),Selection Sort (2),template void selsort(Elem A, int n) for (int i=0; ii; j-) / Find least if (Comp:lt(Aj, Alowindex) lowindex = j; / Put it in place swap(A, i, lowindex
3、); Best Case: Worst Case: Average Case:,Pointer Swapping,Summary,Exchange Sorting,All of the sorts so far rely on exchanges of adjacent records. What is the average number of exchanges required? There are n! permutations Consider permuation X and its reverse, X Together, every pair requires n(n-1)/2
4、 exchanges.,Shellsort,Shellsort,/ Modified version of Insertion Sort template void inssort2(Elem A, int n, int incr) for (int i=incr; i=incr) ,Quicksort,template void qsort(Elem A, int i, int j) if (j (A, i-1, j, Aj); swap(A, k, j); / Put pivot in place qsort(A, i, k-1); qsort(A, k+1, j); template i
5、nt findpivot(Elem A, int i, int j) return (i+j)/2; ,Quicksort Partition,template int partition(Elem A, int l, int r, Elem / Return first pos on right The cost for partition is Q(n).,Partition Example,Quicksort Example,Cost of Quicksort,Best case: Always partition in half. Worst case: Bad partition.
6、Average case: T(n) = n + 1 + 1/(n-1) (T(k) + T(n-k) Optimizations for Quicksort: Better Pivot Better algorithm for small sublists Eliminate recursion,k=1,n-1,Mergesort,List mergesort(List inlist) if (inlist.length() = 1)return inlist; List l1 = half of the items from inlist; List l2 = other half of
7、items from inlist; return merge(mergesort(l1), mergesort(l2); ,Mergesort Implementation,template void mergesort(Elem A, Elem temp, int left, int right) int mid = (left+right)/2; if (left = right) return; mergesort(A, temp, left, mid); mergesort(A, temp, mid+1, right); for (int i=left; i right) / Rig
8、ht exhausted Acurr = tempi1+; else if (Comp:lt(tempi1, tempi2) Acurr = tempi1+; else Acurr = tempi2+; ,Optimized Mergesort,template void mergesort(Elem A, Elem temp, int left, int right) if (right-left) ( ,Mergesort Cost,Mergesort cost: Mergsort is also good for sorting linked lists. Mergesort requi
9、res twice the space.,Heapsort,template void heapsort(Elem A, int n) / Heapsort Elem mval; maxheap H(A, n, n); for (int i=0; in; i+) / Now sort H.removemax(mval); / Put max at end Use a max-heap, so that elements end up sorted within the array. Cost of heapsort: Cost of finding K largest elements:,He
10、apsort Example (1),Heapsort Example (2),Binsort (1),A simple, efficient sort: for (i=0; in; i+) BAi = Ai; Ways to generalize: Make each bin the head of a list. Allow more keys than records.,Binsort (2),template void binsort(Elem A, int n) List BMaxKeyValue; Elem item; for (i=0; in; i+) BAi.append(Ai
11、); for (i=0; iMaxKeyValue; i+) for (Bi.setStart(); Bi.getValue(item); Bi.next() output(item); Cost:,Radix Sort (1),Radix Sort (2),template void radix(Elem A, Elem B, int n, int k, int r, int cnt) / cnti stores # of records in bini int j; for (int i=0, rtok=1; i=0; j-) B-cnt(Aj/rtok)%r = Aj; for (j=0
12、; jn; j+) Aj = Bj; ,Radix Sort Example,Radix Sort Cost,Cost: Q(nk + rk) How do n, k, and r relate? If key range is small, then this can be Q(n). If there are n distinct keys, then the length of a key must be at least log n. Thus, Radix Sort is Q(n log n) in general case,Empirical Comparison (1),Empi
13、rical Comparison (2),Sorting Lower Bound,We would like to know a lower bound for all possible sorting algorithms. Sorting is O(n log n) (average, worst cases) because we know of algorithms with this upper bound. Sorting I/O takes (n) time. We will now prove (n log n) lower bound for sorting.,Decisio
14、n Trees,Lower Bound Proof,There are n! permutations. A sorting algorithm can be viewed as determining which permutation has been input. Each leaf node of the decision tree corresponds to one permutation. A tree with n nodes has W(log n) levels, so the tree with n! leaves has W(log n!) = W(n log n) levels. Which node in the decision tree corresponds to the worst case?,