2008级计算机 内部资料,仅供课堂教学使用 o The best case for contiguous insertion sort occurs when the list is already in order, when insertion sort does nothing except n-l comparisons of keys The worst case for contiguous insertion sort occurs when the list is in reverse order THEOREM 8. 1: Verifying that a list of n entries is in the correct order requires at least n-l comparisons of Insertion sort verifies that a list is correctly sorted as quickly as any method can 18.3 Selection Sort 8.3.1 Example 33 General step: P 330 8.3.2 Selection sort: P. 331 Find maximum key: P 331 Swap entries: P. 33 8.3.3 and 8.3.4 Analysis and comparison P 332 18.4 Shell Sort P. 333 Example of Shell Sort P. 334 Shell Sort P. 335 18.51 Lower bounds P.336 How fast is it possible to sort? THEOREM 8.2: Any algorithm that sorts a list of n entries by use of key comparisons must, in its worst case, perform at least ceiling(lg n!) comparisons of keys, and, in the average case, it must perform at least Ig n comparisons of keys 18.6 Divide-and-Conquer Sorting 8.6.1 Outline P. 339 Mergesort: P. 339 We chop the list into two sublists of sizes as nearly equal as possible and then sort them separately Afterward, we carefully merge the two sorted sublists into a single sorted list Quicksort: P 339-340 We first choose some key from the list for which, we hope, about half the keys will come before and half after. Call this key the pivot. Then we partition the items so that all those with keys less than the pivot come in one sublist, and all those with greater keys come in another. Then we sort the two reduced lists separately, put the sublists together, and the whole list will be in order 8.6.2 mergesort of 7 Numbers P 341 Quicksort of 7 Numbers P 342-344 18.7 Mergesort for Linked Lists 8.7.1 Interface method: P 345 Recursive function P. 345 ivide Linked List in Half P. 346 Merge Function P. 347 8.7.2 Analysis of Mergesort P. 348 Ig n! a n Ig n-144n +o(log n) Mergesort nlgn-1.1583n+1 Insertion sort: n/4+ 0(n) 18.8| Quicksort for Contig uo us Lists 8.8.1 Interface method: P. 353 Recursive function: P. 353 8.8.2 Goal (postcondition ): P. 354 Loop invariant: P 354 Restore the invariant: P. 354 Final position: P 354 Partitioning the List P. 355 8.8.3 Analysis of Quicksort P. 356 Worst-case analysis If the pivot is chosen poorly, one of the partitioned sublists may be empty and the other reduced by only one Choin entry. In this case, quicksort is slower than either insertion sort or selection sort of pivot: First or last entry: Worst case appears for a list already sorted or in reverse order Central entry: Poor cases appear only for unusual orders Random entry: Poor cases are very unlikely Avera analysis In its average case, quick sort performs C(n) =2n In n+O(n)a 1.39n Ig n+O(n) comparisons of keys in sorting a list of n entries in random order. 18.9 Heaps and Heapsort 8.9.1 Trees, Lists, and Heaps P 363-364 e If the root of the tree is in position 0 of the list, then the left and right children of the node in position k are in positions 2k+l and 2k+2 of the list, respectively. If these positions are beyond the end of the list, then these children do not exist2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 ⚫ The best case for contiguous insertion sort occurs when the list is already in order, when insertion sort does nothing except n−1 comparisons of keys. ⚫ The worst case for contiguous insertion sort occurs when the list is in reverse order. THEO REM 8.1: Verifying that a list of n entries is in t he correct order requires at least n−1 comparisons of keys. ⚫ Insertion sort verifies that a list is correctly sorted as quickly as any method can. [8.3] Selection Sort 8.3.1 Example: P. 330 General step: P. 330 8.3.2 Selection sort: P. 331 Find maximum key: P. 331 Swap entries: P. 331 8.3.3 and 8.3.4 Analysis and comparison P. 332 [8.4] Shell Sort P. 333 Example of Shell Sort P. 334 Shell Sort P. 335 [8.5] Lower Bounds P. 336 How fast is it possible to sort? THEO REM 8.2: Any algorithm that sorts a list of n entries by use of key comparisons must, in its worst case, perform at least ceiling(lg n!) comparisons of keys, and, in the average case, it must perform at least lg n! comparisons of keys. [8.6] Divide-and-C onquer Sorting 8.6.1 Outline: P. 339 Mergesort: P. 339 We chop the list into two sublists of sizes as nearly equal as possible and then sort them separately. Afterward, we carefully merge the two sorted sublists into a single sorted list. Quicksort: P. 339-340 We first choose some key from the list for which, we hope, about half the keys will come before and half after. Call this key the pivot. Then we partition the items so that all those with keys less than the pivot come in one sublist, and all those with greater keys come in another. Then we sort the two reduced lists separately, put the sublists together, and the whole list will be in order. 8.6.2 mergesort of 7 Numbers P. 341 Quicksort of 7 Numbers P. 342-344 [8.7] Mergesort for Linked Lists 8.7.1 Interface method: P. 345 Recursive function: P. 345 Divide Linked List in Half P. 346 Merge Function P. 347 8.7.2 Analysis of Mergesort P. 348 Lower bound: lg n! ≈ n lg n − 1.44n + O (log n) Mergesort: n lg n − 1.1583n + 1, Insertion sort: n 2 /4+ O (n) [8.8] Quicksort for Contiguous Lists 8.8.1 Interface method: P. 353 Recursive function: P. 353 8.8.2 Goal (postcondition): P. 354 Loop invariant: P. 354 Restore the invariant: P. 354 Final position: P. 354 Partitioning the List P. 355 8.8.3 Analysis of Quicksort P. 356 Worst-case analysis: If the pivot is chosen poorly, one of the partitioned sublists may be empty and the other reduced by only one entry. In this case, quicksort is slower than either insertion sort or selection sort. Choice of pivot: ⚫ First or last entry: Worst case appears for a list already sorted or in reverse order. ⚫ Central entry: Poor cases appear only for unusual orders. ⚫ Random entry: Poor cases are very unlikely to occur. Average-case analysis: In its average case, quicksort performs C(n) = 2n ln n + O (n) ≈ 1.39n lg n + O (n) comparisons of keys in sorting a list of n entries in random order. [8.9] Heaps and Heapsort 8.9.1 Trees, Lists, and Heaps P. 363-364 ⚫ If the root of the tree is in position 0 of the list, then the left and right children of the node in position k are in positions 2k+1 and 2k+2 of the list, respectively. If these positions are beyond the end of the list, then these children do not exist