2008级计算机专业数据结构课 供课堂教学使用 Chapter 8 Sorting P317 -------- 1. Introduction and Notation 6. Divide-and-Conquer Sorting 2. Insertion Sort 7. Mergesort for Linked Lists 3. Selection Sort 8. Quicksort for Contiguous Lists 4. Shell Sort 9. Heaps and Heapsort 5. Lower Bounds 10. Review: Comparison of Method 18. 1 Introd uction and Notation e In an external sort, there are so many records to be sorted that they must be kept in external files on disks, tapes, or the like. In an internal sort the records can all be kept internally in high-speed memory. We consider only internal sorting e We use the notation and classes set up in Chapters 6 and 7. Thus we shall sort lists of records into the order determined by keys associated with the records. The declarations for a list and the names assigned to various types and operations will be the same as in previous chapters If two or more of the entries in a list have the same key, we must exercise special care To analyze sorting al gorithms, we consider both the number of comparisons of keys and the number of times entries must be moved inside a list, particul arly in a contiguous list Both the worst-case and the average performance of a sorting algorithm are of interest. To find the average, we shall consider what would happen if the al gorithm were run on all possible orderings of the list 8, ( with n entries, there are n! such orderings altogether) and take the average of the result 1.1 Sortable Lists P 319 To write efficient sorting programs, we must access the private data members of the lists being sorted herefore, we shall add sorting functions as methods of our basic list data structur structure forms a new adt that we shall call a Sortable List, with the following form S. The augmented list template 4 public: /Add prototypes for sorting methods here private: // Add prototy pes for auxiliary functions here Hence a Sortable list is a List with extra sorting methods e The base list class can be any of the List implementations of Chapter 6 We use a template parameter class called Record to stand for entries of the Sortable list. Every Record has an associated key of type Key. A Record can be implicitly converted to the corresponding Key. The keys(hence also the records)can be compared under the operations ' e Any of the Record implementations discussed in Chapter 7 can be supplied, by a client, as the template parameter of a Sortable list 18.2 Insertion Sort 8.2.1 Ordered Insertion P. 320 An ordered list is an abstract data type, defined as a list in which each entry has a key, and such that the keys are in order; that is, if entry i comes before entry j in the list, then the key of entry i is less than or equal to the key of entry j For ordered lists, we shall often use two new operations that have no counterparts for other lists, since they use keys rather than positions to locate the entry One operation retrieves an entry with a specified key from the ordered list. Retrieval by key from an ordered list is exactly the same as searching u The second operation, ordered insertion, inserts a new entry into an ordered list by using the key in the new entry to determine where in the list to insert it o Note that ordered insertion is not uniquely specified if the list already contains an entry with the same key as the new entry, since the new entry could go into more than one position. P. 321 8.2.2 Insertion Sort Example P 322 Contiguous Insertion Sort P. 322 Main step, contiguous case: P 323 8.2.3 Linked Insertion Sort P. 323-325 8.2.4 Analysis of Insertion Sort P 325-327 The average number of comparisons for insertion sort applied to a list of n items in random order is n/4+ e The average number of assignments of items for insertion sort applied to a list of n items in random order is also n /4+ O(n)
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 Chapter 8 Sorting P.317 ----------------------------------------------------------------------------------------------------------------------------- ------- 1. Introduction and Notation 2. Insertion Sort 3. Selection Sort 4. Shell Sort 5. Lower Bounds 6. Divide-and-Conquer Sorting 7. Mergesort for Linked Lists 8. Quicksort for Contiguous Lists 9. Heaps and Heapsort 10.Review: Comparison of Methods [8.1] Introduction and Notation Requirements ⚫ In an external sort, there are so many records to be sorte d that they must be kept in external files on disks, tapes, or the like. In an internal sort the records can all be kept internally in high -speed memory. We consider only internal sorting. ⚫ We use the notation and classes set up in Chapters 6 and 7. Thus we shall sort lists of records into the order determined by keys associated with the records. The declarations for a list and the names assigned to various types and operations will be the same as in previous chapters. ⚫ If two or more of the entries in a list have the same key, we must exercise special care. ⚫ To analyze sorting algorithms, we consider both the number of comparisons of keys and the number of times entries must be moved inside a list, particularly in a contiguous list. ⚫ Both the worst-case and the average performance of a sorting algorithm are of interest. To find the average, we shall consider what would happen if the algorithm were run on all possible orderings of the list (with n entries, there are n! such orderings altogether) and take the average of the results. 8.1.1 Sortable Lists P. 319 ⚫ To write efficient sorting programs, we must access the private data members of the lists being sorted. Therefore, we shall add sorting functions as methods of our basic List data structures. The augmente d list structure forms a new ADT that we shall call a Sortable_List, with the following form. template class Sortable_list: public List { public: //Add prototypes for sorting methods here. private: // Add prototypes for auxiliary functions here. }; ⚫ Hence a Sortable_list is a List with extra sorting methods. ⚫ The base list class can be any of the List implementations of Chapter 6. ⚫ We use a template parameter class called Record to stand for entries of the Sortable_list. Every Record has an associated key of type Key. A Record can be implicitly converted to the corresponding Key. The keys (hence also the records) can be compared under the operations ‘’ , ‘>=’ , ‘<=’ , ‘==’ ,and ‘!=’. ⚫ Any of the Record implementations discussed in Chapter 7 can be supplied, by a client, as the template parameter of a Sortable_list. [8.2] Insertion Sort 8.2.1 Ordered Insertion P. 320 ⚫ An ordered list is an abstract data type, defined as a list in which each entry has a key, and such that the keys are in order; that is, if entry i comes before entry j in the list, then the key of entry i is less than or equal to the key of entry j . ⚫ For ordered lists, we shall often use two new operations that have no counterparts for other lists, since they use keys rather than positions to locate the entry. ◼ One operation retrieves an entry with a specified key from the ordered list. Retrieval by key from an ordered list is exactly the same as searching. ◼ The second operation, ordered insertion, inserts a new entry into an ordered list by using the key in the new entry to determine where in the list to insert it. ⚫ Note that ordered insertion is not uniquely specified if the list already contains an entry with the same key as the new entry, since the new entry could go into more than one position. P. 321 8.2.2 Insertion Sort Example P. 322 Contiguous Insertion Sort P. 322 Main step, contiguous case: P. 323 8.2.3 Linked Insertion Sort P. 323-325 8.2.4 Analysis of Insertion Sort P. 325-327 ⚫ The average number of comparisons for insertion sort applied to a list of n items in random order is n 2 /4 + O(n). ⚫ The average number of assignments of items for insertion sort applied to a list of n items in random order is also n2 /4+ O(n)
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 exist
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 ⚫ 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
2008级计算机 内部资料,仅供课堂教学使用 DEFINITION: A heap is a list in which each entry contains a key, and, for all positions k in the list, the key at position k is at least as large as the keys in positions 2k and 2k+ 1, provided these positions exist in the list REMARK Many C++ manuals and textbooks refer to the area used for dynamic memory as the"heap", this use of the word"heap"has nothing to do with the present definition o Heapsort is suitable only for contiguous lists 8.9.2 Trace of heapsort P.364-367 Main function for heapsort P 365 Insertion into a heap: P 366 Building the initial heap: P. 368 8.9.3 Analysis of Heapsort P 368-369 In its worst case for sorting a list of length n, heapsort performs 2n Ig n o(n)comparisons of keys, and it performs n Ig n +o(n) assignments of entries 8.9.4 Priority DEFINITION: A priority queue consists of entries, such that each entry contains a key called the priority of the entry. A priority queue has only two operations other than the usual creation clearing, size, full, and empty operations Insert an entry. Remove the entry having the largest (or smallest) key If entries have equal keys, then any entry with the largest key may be removed first 18.10| Review: Comp arison of Methods P 372 Comparison of Sorting Methods P372-374 Use of space Use of computer time Programming effort Statistical analysis Empirical testing Pointers and Pitfalls 6 items F.375-376 Errata 324. UseS: line: Change "Record. The to "Record. the 331, "Uses: line of max key: Change "Record. The"to"Record, the p 334, Fig. 8.7: The arrow shafts are missing in the 3-Sorted"column. p. 362, E8(f): Insert a semicolon " "after "swap(i,j) p.371,E6. Change"lg(n+1)/(k+1))"to"lg(n/(k+1)
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 DEFINITION: A heap is a list in which each entry contains a key, and, for all positions k in the list, the key at position k is at least as large as the keys in positions 2k and 2k + 1, provided these positions exist in the list. ⚫ REMARK Many C++ manuals and textbooks refer to the area used for dynamic memory as the “heap”; this use of the word “heap” has nothing to do with the present definition. ⚫ Heapsort is suitable only for contiguous lists. 8.9.2 Trace of heapsort P. 364-367 Main function for heapsort P. 365 Insertion into a heap: P. 366 Building the initial heap: P. 368 8.9.3 Analysis of Heapsort P. 368-369 In its worst case for sorting a list of length n, heapsort performs 2n lg n + O(n) comparisons of keys, and it performs n lg n + O (n) assignments of entries. 8.9.4 Priority Queues P. 369 DEFINITION: A priority queue consists of entries, such that each entry contains a key called the priority of the entry. A priority queue has only two operations other than the usual creation, clearing, size, full, and empty operations: Insert an entry. Remove the entry having the largest (or smallest) key. If entries have equal keys, then any entry with the largest key may be removed first. [8.10] Review: Comparison of Methods P.372 Comparison of Sorting Methods P.372-374 ⚫ Use of space ⚫ Use of computer time ⚫ Programming effort ⚫ Statistical analysis ⚫ Empirical testing Pointers and Pitfalls 6 items P.375-376 ------------------------------------------------------------------------------------------------------------------------------- Errata p. 324, "Uses:" line: Change "Record. The" to "Record, the". p. 331, "Uses:" line of max_key: Change "Record. The" to "Record, the". p. 334, Fig. 8.7: The arrow shafts are missing in the "3-Sorted" column. p. 362, E8(f): Insert a semicolon ";" after "swap(i,j)". p. 371, E6: Change "lg((n+1)/(k+1))" to "lg(n/(k+1))". -------------------------------------------------------------------------------------------------------------------------------