Contiguous Insertion Sort template <class Record> void Sortable_ list<Record> insertion sort() i int first_unsorted, position; Record current: pp Find't current entrie proper position for(first_unsorted=1; firs_uns if(entry[first_unsortedleTtxc i position=firet Torted; current -entry[first_unsorted seard s sorted dof entry[position]=entry/pr tion-1 t of list position--; 3 while(position>D/&& entry[position-1]>current) entrylposition]=current;
Contiguous Insertion Sort template <class Record> void Sortable_list<Record>::insertion_sort( ) { int first_unsorted, position; Record current; for(first_unsorted = 1; first_unsorted < count; first_unsorted++) if(entry[first_unsorted] < entry[first_unsorted-1]) { position = first_unsorted; current = entry[first_unsorted]; do{ entry[position] = entry[position-1]; position--; } while(position>0 && entry[position-1]>current); entry[position] = current; } } position of first unsorted entry searches sorted part of list Pull unsorted entry out of the list. Shift all entries until the proper position is found position is not empty current entry store proper position Find’t current entries
Linked Insertion Sort With no movement of data, there is no need to search from the end of the sorted sublist as for the contiguous case Traverse the original list, taking one entry at a time and inserting it in the proper position in the sorted list. Pointer last sorted references the end of the sorted part of the list Pointer first unsorted==last sorted->next references the first entry that has not yet been inserted into the sorted sublist Pointer current searches the sorted part of the list to find where to insert first unsorted CIf* first unsorted belongs before the head of the list, then insert it there
Linked Insertion Sort ◆With no movement of data, there is no need to search from the end of the sorted sublist, as for the contiguous case. ◆Traverse the original list, taking one entry at a time and inserting it in the proper position in the sorted list. ◆Pointer last sorted references the end of the sorted part of the list. ◆Pointer first_unsorted==last_sorted->next references the first entry that has not yet been inserted into the sorted sublist. ◆Pointer current searches the sorted part of the list to find where to insert *first_unsorted. ◆If * first_unsorted belongs before the head of the list, then insert it there
Otherwise, move current down the list until first unsorted->entry < current->entry and then insert s first unsorted before current to enable insertion before*current keep a second pointer trailing in lock step one position closer to the head than current A sentinel is an extra entry added to one end of a list to ensure that a loop will terminate without having to include a separate check. since last sorted- >next = first_ unsorted, the node first unsorted is already in position to serve as a sentinel for the search and the loop moving current is simplified A list with o or 1 entry is already sorted, so by checking these cases separately we avoid trivialities elsewhere
◆Otherwise, move current down the list until first_unsorted->entry <= current->entry and then insert * first_unsorted before *current. To enable insertion before *current, keep a second pointer trailing in lock step one position closer to the head than current. ◆A sentinel is an extra entry added to one end of a list to ensure that a loop will terminate without having to include a separate check. Since last_sorted->next == first_unsorted , the node * first_unsorted is already in position to serve as a sentinel for the search, and the loop moving current is simplified. ◆A list with 0 or 1 entry is already sorted, so by checking these cases separately we avoid trivialities elsewhere
template <class Reinsert*first_unsorted void Sortable I at the head of she ep Search the sorted I Node<Record>ms the sorted list sublist to insert first unsorted if(head=NU山) last sorted d while(last orted->next != NULL used to/ erse I first /unsorted= last_sortenext; the one position if(first_unsorted->en* head->entry) behind current I last_ sorted->axt= first_unsorted->next; first_unsarted->next= head; head first_unsorted; first unsorted else now belongs between trailing=head; current=+ * trailing and * current whilefirst_unsorted-rrcry current->entry) I trailing current; current =trailing->next; 1
template <class Record> void Sortable_list<Record>::insertion_sort( ) { Node<Record> *first_unsorted, *last_sorted, *current, *trailing; if(head == NULL) return; last_sorted = head; while(last_sorted->next != NULL) { first_unsorted = last_sorted->next; if(first_unsorted->entry < head->entry) { last_sorted->next = first_unsorted->next; first_unsorted->next = head; head = first_unsorted; } else { trailing = head; current = trailing->next; while(first_unsorted->entry > current->entry) { trailing = current; current = trailing->next; } the first unsorted node to be inserted tail of the sorted sublist used to traverse the sorted sublist one position behind current the empty list is already sorted The first node alone makes a sorted sublist Insert *first_unsorted at the head of the sorted list Search the sorted sublist to insert*first_unsorted *first_unsorted now belongs between *trailing and *current
if(first unsorted = current) last sorted first unsorted else f last sorted->next=first unsorted->next; first unsorted->next current trailing->next= first unsorted Partially sorted Case 1: first unsorted belongs at head of list head last sorted first unsorted …闻丫 Case 2:first_ unsorted belongs between'trailing and current head trailing current last sorted first unsorted --… -
if(first_unsorted == current) last_sorted = first_unsorted; else { last_sorted->next = first_unsorted->next; first_unsorted->next = current; trailing->next = first_unsorted; } } // end_above else( if-else block) } // end_while } // end_function