shell.cpp

数据结构与程序设计教材源码 数据结构与程序设计教材源码

 
template <class Record>
void Sortable_list<Record>::sort_interval(int start, int increment)
/* 
 
Pre:   start is a valid list position and increment is a valid stepping length.
Post: The entries of the Sortable_list have been rearranged so that the keys in all the
      entries are sorted into nondecreasing order based on certain positions
      calculated by start and increment.
Uses: Methods for classes Record and Key.
      The contiguous List implementation of ?list_ch?.
 
*/

{
   int first_unsorted;    //  position of first unsorted entry
   int place;             //  searches sorted part of list
   Record current;        //  used to swap entries

   for (first_unsorted = start + increment; first_unsorted < count; first_unsorted += increment)
      if (entry[first_unsorted] < entry[first_unsorted - increment]) {
         place = first_unsorted;
         current = entry[first_unsorted];   //  Pull entry[first_unsorted] out of the list.
         do {                           //  Shift all previous entries one place down the list
            entry[place] = entry[place - increment];     //  until the proper place is found.
            place -= increment;             //  Position place is now available for insertion.
         } while (place > start && entry[place - increment] > current);
         entry[place] = current;
      }
}
 
template <class Record>
void Sortable_list<Record>::shell_sort()
/* 
 
Post: The entries of the Sortable_list have been rearranged so that the keys in all the
      entries are sorted into nondecreasing order.
Uses: sort_interval
 
*/

{
   int increment,    //  spacing of entries in sublist
       start;        //  starting point of sublist
   increment = count;

   do {
      increment = increment / 3 + 1;
      for (start = 0; start < increment; start++)
         sort_interval(start, increment);  //  modified insertion sort
   } while (increment > 1);
}