Chapter 8 SORTING 1 Introduction and Notation 2. Insertion Sort I3 Selection Sort 4. Shell Sort 5. Lower Bounds 6. Divide-and-Conquer Sorting
Chapter 8 SORTING 1. Introduction and Notation 2. Insertion Sort 3. Selection Sort 4. Shell Sort 5. Lower Bounds 6. Divide-and-Conquer Sorting
Chapter 8 SORTING(continue) 7. Mergesort for Linked Lists 8. Quicksort for Contiguous Lists 9. Heaps and Heapsort I10. Comparison of Methods 1 1. Pointers and pitfalls
Chapter 8 SORTING (continue) 8. Quicksort for Contiguous Lists 9. Heaps and Heapsort 10. Comparison of Methods 11. Pointers and Pitfalls 7. Mergesort for Linked Lists
8.1 Introduction and notation 9In an external sort there are so many records to be sorted that they must be kept in external les 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
8.1 Introduction and notation ◆In an external sort, there are so many records to be sorted that they must be kept in external les 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
C 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, particularl 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
◆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
Sortable lists 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 augmented list structure forms a new adt that we shall call a Sortable List with the following form template <class record> class sortable list: public List<Record i public: / Add prototypes for sorting methods here. private: / Add prototypes for auxiliary functions here
Sortable Lists ◆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 augmented list structure forms a new ADT that we shall call a Sortable_List, with the following form. template <class Record> class Sortable_list:public List<Record> { public: // Add prototypes for sorting methods here. private: // Add prototypes for auxiliary functions here. };