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 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 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 C Record objects can be compared to each other or to a Key by first converting the record objects to their
◆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. ◆Record objects can be compared to each other or to a Key by first converting the Record objects to their
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 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 jin the list, then the key of entry i is less than or equal to the key of entry j
◆Any of the Record implementations discussed in Chapter 7 can be supplied, by a client, as the template parameter of a Sortable_list. ◆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 . 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 ' !=
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. o 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. oThe 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
•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. ◆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
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 cat cat cat cat COW COW COW COW do dog dog dog pIg pIg hen hen ram pIg pig Ordered ram ram ram entry Move Move Complete last entry previous insertion entry
◆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
8.2 Insertion Sort Example: Init ial Insert Insen Insert Insert order second t hird fourth Fifth sixth entry entry entry entry entry sorted hen cat cat cat sorted unsorted co hen cow cow cat hen hen dog ram ram ram ram hen ewe ewe ewe ewe ewe ram he sorted dog dog dog do ram Main step, contiguous case: Before rtel Unrted s current s current Remoe current sIlt entries nu lt Sorted Sorted Vertex current Reinert current Sorted Reourtel
8.2 Insertion Sort
