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