The La Plata Mountains as seen from above the author’s
            home.


Durango Bill’s

“C” Program to implement Sort Algorithms
(Source Code)



Return to the main Sort page

Web page generated via Sea Monkey's Composer HTML editor
within  a Linux Cinnamon Mint 18 operating system.
(Goodbye Microsoft)




//************* ********************* ************************* *****************
//
//                                Sort Algorithms
//                                      by
//                                  Bill Butler
//
//  This program can execute various sort algorithms to test how fast they run.
//
//  Sorting algorithms include:
//  Bubble sort
//  Insertion sort
//  Median-of-three quicksort
//  Multiple link list sort
//  Shell sort
//
//  For each of the above, the user can generate up to 10 million random
//  integers to sort. (Uses a pseudo random number generator so that the list
//  to sort can be exactly regenerated.)
//  The program also times how long each sort takes.
//
//************ ********************** ******************** *******************


#include <stdheaders.h>                      //  The usual stdio.h, etc.

void GenRandom(void);                        //  Generate a list of random nbrs.
void BubbleSort(void);                       //  Bubble Sort
void InsertionSort(void);                    //  Insertion Sort
void MLLsort(void);                          //  Multiple Link List Sort
void QuickSort(void);                        //  Median-of-three Quicksort
void ShellSort(void);                        //  Choose from 3 gap sequences

void PauseMsg(void);                         //  Pause the screen display


unsigned RandNbrs[10000004];                 //  The list of random numbers
                                             //  will be generated here. Note:
                                             //  RandNbrs[0] is used as a sentinel
int MLLlinks[26777220];                      //  Used by MLLsort. Will use up to
                                             //  10,000,000 + 2^24 + 1 of this
int QSleft[30];                              //  Stack arrays for the left/right
int QSright[30];                             //  ends of subgroups within
                                             //  QuickSort()
int Gaps13[24] = {0, 1, 3, 7, 21, 48, 112,   //  Three possible gap sequences
    336, 861, 1968, 4592, 13776, 33936,      //  may be used for experiments
    86961, 198768, 463792, 1391376,          //  with Shell Sort.
    3402672, 8382192, 21479367, 49095696,    //  See Sedgewick & ATT database
    114556624, 343669872};                   //  of integers for more info

int Gaps18[24] = {0, 1, 8, 23, 77, 281,      //  Gaps[i+2] = 4^(i+1) + 3*(2^i) + 1
    1073, 4193, 16577, 65921, 262913,
    1050113, 4197377, 16783361, 67121153,
    268460033, 1073790977};

int Gaps14[24] = {0, 1, 4, 13, 40, 121, 364, //  Gaps[i+1] = 3*Gaps[i] + 1
    1093, 3280, 9841, 29524, 88573, 265720,
    797161, 2391484, 7174453, 21523360,
    64570081, 193710244, 581130733, 1743392200};

int Gaps[24];                                //  Will copy one of the above into
                                             //  here.

int Nbr2Sort;                                //  Number of items to sort.

char Databuff[100];                          //  Buffer for user input (Assumes
                                             //  user does not abuse size)



int main(void) {

  int choice;

  puts("\nThis program demonstrates the performance of various sort algorithms.");
  puts("You may run time trials to compare results.\n");
  puts("Note: If you want to use identical inputs for the time trials,");
  puts("just use the same seed number for the random number generator.\n");
  PauseMsg();

  while(1) {                                //  Loop until user ends program
    puts("\n\n     *****     Enter number for menu choice     *****\n");
    puts("1)  Bubble sort");
    puts("2)  Insertion sort");
    puts("3)  Median-of-three Quicksort");
    puts("4)  Multiple link list sort");
    puts("5)  Shellsort (Choice of 3 different shell definitions)");
    puts("6)  End the program\n");

    gets(Databuff);
    choice = atoi(Databuff);

    if (choice == 6)
      break;

    GenRandom();                            //  Generate a list of random nbrs

    if (choice == 1) BubbleSort();
    else if (choice == 2) InsertionSort();
    else if (choice == 3) QuickSort();
    else if (choice == 4) MLLsort();
    else if (choice == 5) ShellSort();
  }
  return 0;
}



 
//************** ********************* *********************** ******************
//
//                                GenRandom
//
//  This routine generates a list of unsigned random integers in the range 0 to
//  4,294,967,295. An exact repetion of any list can be regenerated by using
//  the same seed number and the same quantity of numbers. Up to 10 million
//  numbers can be generated in the array RandNbrs[].
//
//  The random numbers will occupy positions RandNbrs[1] to RandNbrs[Nbr2Sort].
//  Nothing is placed in RandNbrs[0], but RandNbrs[0] will be used by some of
//  the sort routines to optimize execution speed.
//
//************** ******************** ************************** *****************

void GenRandom(void) {

  int i;
  unsigned seed;
  unsigned Multiplier;

  do {
    puts("\nEnter number of elements to sort (3 - 10,000,000)");
    gets(Databuff);
    Nbr2Sort = atoi(Databuff);
  } while ((Nbr2Sort < 3) || (Nbr2Sort > 10000000));

  puts("\nEnter a seed number for the random number generator");
  gets(Databuff);
  seed = atoi(Databuff);

  Multiplier = 3141592621;
  for (i = Nbr2Sort; i; i--) {                //  Fill array with random
    seed *= Multiplier;                       //  numbers.
    seed++;
    RandNbrs[i] = seed;
  }

  puts("\nDo you want to see the random numbers before they are sorted (Y or N)?");
  gets(Databuff);
  if (tolower(Databuff[0]) == 'y') {
    puts("");
    for (i = 1; i <= Nbr2Sort; i++) {
      printf("%4d) %'16u\n",i , RandNbrs[i]);
      if (!(i%20))                            //  Keeps list from running
        PauseMsg();                           //  off top of screen.
    }
    PauseMsg();
  }
}




//**************** ********************** ********************** ***************
//
//                                Bubble Sort
//
//  Bubble sort is not exactly the world's fastest sorting algorithm, but for
//  some reason, everyone seems to like it. Maybe it's related to:
//
//  "Tiny Bubbles"
//  "In the wine"
//  "Make you feel happy"
//  "Make you feel fine"
//
//  This version of Bubble Sort will sort the array RandNbrs[] in ascending
//  order. When the routine is finished, the lowest number in the RandNbrs[]
//  array will be found in position RandNbrs[1] while the largest number will
//  be in position RandNbrs[Nbr2Sort].
//
//  The algorithm starts by looking at positions 1 and 2 in the array. If the
//  number at position 1 is larger than the number at position 2, then the two
//  numbers are exchanged. The end result will leave the larger of the two
//  numbers at position 2 and the smaller at position 1.
//
//  After the above step, the algorithm looks at the numbers at positions 2 and
//  3. If the number at position 2 is larger, then it is exchanged so that the
//  larger number will now be in position 3.
//
//  The "j" loop continues this process until it reaches the bottom (highest
//  index location) of the array. At this point the largest number in the array
//  has been moved to the bottom of the array, and everything else has "bubbled"
//  up one level. Then, the "i" loop exerts control and the whole process
//  repeats. However, this time through, the 2nd largest number in the array
//  will be shifted down to the 2nd lowest position in the array. (Again this
//  stopping point is controled by the "i" loop.)
//
//  By the time "i" decreases to 1, the whole array is sorted.
//
//**************** ********************* *********************** *****************

void BubbleSort(void) {

  int i, j, k;
  unsigned temp;
  double Time1, Time2;

  puts("\nStarting Bubble Sort");

  Time1 = (double)clock();                        //  Save time to 0.001 sec.
  Time1 = Time1/(double)CLOCKS_PER_SEC;

  for (i = Nbr2Sort - 1; i; i--) {
    for (j = 1, k = 2; j <= i; j++, k++) {
      if (RandNbrs[j] > RandNbrs[k]) {
        temp = RandNbrs[j];
        RandNbrs[j] = RandNbrs[k];
        RandNbrs[k] = temp;
      }
    }
  }

  Time2 = (double)clock();
  Time2 = Time2/(double)CLOCKS_PER_SEC;

  printf("\nThe time to sort %'d items via Bubble Sort was %g seconds.\n",
    Nbr2Sort, Time2 - Time1);

  PauseMsg();

  puts("\nDo you want to see the random numbers after they were sorted (Y or N)?");
  gets(Databuff);
  if (tolower(Databuff[0]) == 'y') {
    puts("");
    for (i = 1; i <= Nbr2Sort; i++) {
      printf("%4d) %'16u\n", i, RandNbrs[i]);
      if (!(i%20))
        PauseMsg();
    }
    PauseMsg();
  }
}




//****************** ******************* *********************** ***************
//
//                                Insertion Sort
//
//  Insertion sort is simple to code and difficult to beat if you are sorting
//  a short list of elements. It is also very good at sorting a much larger
//  list that is nearly in sorted order. It is thus used as the basis of Shell
//  Sort and the final stage of "median-of-three Quicksort".
//
//  Computer processors usually have "on board" cache memories that provide an
//  added boost to Insertion Sort. Portions of the array to be sorted will be
//  stored in the (faster access) cache memory. If an array is nearly sorted
//  when Insertion Sort is called, then most of Insertion Sort's operations
//  will take place inside this high speed cache memory.
//
//  This version of Insertion Sort will sort the array RandNbrs[] in ascending
//  order. When the routine is finished the lowest number in the RandNbrs[]
//  array will be found in position RandNbrs[1] while the largest number will
//  be in position RandNbrs[Nbr2Sort].
//
//  The algorithm starts with some number in place at RandNbrs[1]. Then it
//  moves down to array position 2. The number at position 2 is copied to a
//  temporary holding position in variable "temp". Then all numbers that are in
//  lower index positions in the array and are also larger than what is in
//  "temp" are moved down one position. When a smaller number is encountered,
//  then the number in "temp" is inserted back into the array.
//
//  Next the algorithm works on the number in array position 3. Again all
//  numbers that are larger than what is in "temp" are moved down one position.
//  When a smaller (or equal) number is encounter, the number in "temp" is
//  inserted back into the empty space.
//
//  The algorithm continues in this fashion until it reaches the bottom of
//  the list to be sorted.
//
//************ **************************** ******************* ******************

void InsertionSort(void) {

  int i, j, k;
  unsigned temp;
  double Time1, Time2;

  puts("\nStarting Insertion Sort");

  Time1 = (double)clock();                      //  Save time to 0.001 sec.
  Time1 = Time1/(double)CLOCKS_PER_SEC;

  RandNbrs[0] = 0;            //  Sentinel for sort. Must be <= the lowest
                              //  value that will be sorted. Using a sentinel
                              //  speeds up the algorithm since an additional
                              //  run-off-the-"0"-end-of-the-array test will
                              //  not be needed.

  for (i = 2; i <= Nbr2Sort; i++) {
    k = i;
    j = i - 1;
    temp = RandNbrs[k];
    while (RandNbrs[j] > temp) {
      RandNbrs[k] = RandNbrs[j];
      j--;
      k--;
    }
    RandNbrs[k] = temp;
  }

  Time2 = (double)clock();
  Time2 = Time2/(double)CLOCKS_PER_SEC;

  printf("\nThe time to sort %'d items via Insertion Sort was %g seconds.\n",
    Nbr2Sort, Time2 - Time1);

  PauseMsg();

  puts("\nDo you want to see the random numbers after they were sorted (Y or N)?");
  gets(Databuff);
  if (tolower(Databuff[0]) == 'y') {
    for (i = 1; i <= Nbr2Sort; i++) {
      printf("%4d) %'16u\n", i, RandNbrs[i]);
      if (!(i%20))
        PauseMsg();
    }
    PauseMsg();
  }
}





//************** ******************** *********************** ***************
//
//                                MLLsort
//
//  If the numbers to be sorted are within a known range, and if on average
//  they are distributed approximately evenly, and if you have lots of extra
//  random access memory, then a multiple link list sort may be faster than
//  all other sorting algorithms. In this application, the numbers to be sorted
//  are in the array RandNbrs[]. The sorting algorithm never moves them.
//
//  Instead, for each element to be sorted, its proper sort location is
//  calculated as an index into the MLLlinks[] array. This initial calculated
//  link head address is equal to the sum of the Nbr2Sort plus a calculated
//  distance beyond this index number. The calculated distance can be varied to
//  see what produces the best result.
//
//  The correlation between the RandNbrs[] array and the MLLlinks[] array
//  looks like:
//
//            ------------------------
//  RandNbrs |    |    |    |    |    |
//            ------------------------
//              0    1    2    Nbr2Sort
//
//            --------------------------- -----------------------------------
//  MLLlinks |Link lists for each grp |       Link head for each group      |
//            ---------------------------- ----------------------------------
//             0     1   2     Nbr2Sort  Calculated pos. for each random nbr.
//
//  Once a calculated address is known, a link list is started using this
//  number's calculated addess. If any subsequent RandNbrs[] element ends up
//  using this same calculated address, it is added to the link list for this
//  address. The links in any link list are adjusted for these additions such
//  that the access order will be in sorted order.
//
//*************** ********************** *********************** *************

void MLLsort(void) {

  int HeadBase, i, count;
  unsigned NbrHeads, ShiftAmt, value;
  unsigned ptr1, ptr2;
  double Time1, Time2;

  puts("\nStarting Multiple Link List Sort");

  Time1 = (double)clock();                  //  Save time to 0.001 sec.
  Time1 = Time1/(double)CLOCKS_PER_SEC;

  RandNbrs[0] = 4294967295;                 //  Sentinel for sort.
                                            //  Must be >= the largest
                                            //  number to be sorted.
  HeadBase = Nbr2Sort + 1;
  NbrHeads = 4;                             //  Calculate how many list
  ShiftAmt = 30;                            //  heads and how many bit
  while (NbrHeads < Nbr2Sort) {             //  positions to shift for
    ShiftAmt--;                             //  indexing.
    NbrHeads <<= 1;
  }
                                            //  Optional debug info
//  printf("With %'d numbers to sort the calculated value for NbrHeads is %'d\n",
//        Nbr2Sort, NbrHeads);

  for (i = Nbr2Sort + NbrHeads; i >= HeadBase; i--)
    MLLlinks[i] = 0;                        //  Zero out the link heads. Note:
                                            //  If you are only going to run
                                            //  this routine once, you can take
                                            //  advantage of the built in
                                            //  initialization routines in C
                                            //  and ignore this step.

  for (i = Nbr2Sort; i; i--) {              //  For all input numbers.
    value = RandNbrs[i];                    //  Will calculate where it should
    ptr1 = value;                           //  go. Construct index.
    ptr1 >>= ShiftAmt;
    ptr1 += HeadBase;
                                            //  Search link list to see where
                                            //  to insert this element. Most of
                                            //  the time the new value will be
                                            //  the 1st in the list.
    for (ptr2 = MLLlinks[ptr1]; RandNbrs[ptr2] < value;
        ptr1 = ptr2, ptr2 = MLLlinks[ptr2]);

        //  Note: The average length of these link lists does not increase as
        //  "Nbr2Sort" increases. The processing time per sort element is
        //  a constant that is independent of "Nbr2Sort". Thus the algorithm
        //  runs in pure linear time and not something slower such as
        //  N*log(log(N)) time.

    MLLlinks[ptr1] = i;                     //  Insert location of new
    MLLlinks[i] = ptr2;                     //  value in link list.
  }

  Time2 = (double)clock();
  Time2 = Time2/(double)CLOCKS_PER_SEC;

  printf("\nThe time to sort %'d items via MLL Sort was %g seconds.\n",
    Nbr2Sort, Time2 - Time1);

  PauseMsg();

  puts("\nDo you want to see the random numbers after they were sorted (Y or N)?");
  gets(Databuff);
  if (tolower(Databuff[0]) == 'y') {
    count = 0;
    ptr2 = Nbr2Sort + NbrHeads;
    for (i = HeadBase; i <= ptr2; i++) {
      for (ptr1 = MLLlinks[i]; ptr1; ptr1 = MLLlinks[ptr1]) {
        count++;
        printf("%4d) %'16u\n", count,  RandNbrs[ptr1]);
        if (!(count%20))
          PauseMsg();
      }
    }
    PauseMsg();
  }
}




//*************** ******************** ************************ ******************
//
//                                    QuickSort
//
//  QuickSort has long had a reputation for being the fastest general purpose
//  sort algorithm. It is also perhaps the most difficult to code, and is
//  subject to sharply adverse execution time if the "pivot values" are picked
//  poorly - which can happen if the data to be sorted is already partially
//  sorted.
//
//  The algorithm works by picking one of the elements to be sorted as a "pivot
//  value". The list of items to be sorted is then partitioned so that all
//  elements that have a value less than the pivot end up in the front portion
//  of the array while all elements that are greater than the pivot value end
//  up in the other end. (Elements that are equal to the pivot could end up in
//  either section.) After the first pass, the array of items to be sorted
//  looks like:

//
//                                     Pivot
//             Low elements are here   Item     Higher elements are here
//            -----------------------------------------------------------
//  RandNbrs |    |    |    |    |    |    |    |    |    |    |    |    |
//            -----------------------------------------------------------
//              1    2    3    4                                  Nbr2Sort

//
//  After round 1, the QuickSort process is applied to both of the 2 subgroups.
//  Whichever subgroup was smaller is processed immediately while the location
//  of the left and right ends of the larger subgroup are placed on a stack
//  for later processing. This processing order will guarantee that the stack
//  will never exceed Log2(Nbr2Sort) items.
//
//  The repetitive processing of subgroups continues until the size of a
//  subgroup falls below a size defined by "MinGroup". Once a subgroup is
//  smaller than this, it is not sorted further by QuickSort. Small groups can
//  be processed faster by Insertion Sort. When Quicksort has reduced all
//  subgroups to < "MinGroup" size, control passes to "Insertion Sort" for a
//  final pass through the entire array.
//
//  In the "old days", the optimal size for "MinGroup" was about 18. The cache
//  memory on current processor chips reduces the time to access anything in
//  the cache - which includes the part of the array that is currently residing
//  in the cache. This greatly increases the efficiency of the final "Insertion
//  Sort" relative to the quicksort portion. Thus, significantly larger values
//  for "MinGroup" work better when a cache is being used. (You can experiment
//  with the value that is assigned to "MinGroup".)
//
//  Selection of the "pivot value" is crucial to the efficiency of Quicksort.
//  If the pivot value is selected so that it evenly partitions a subgroup,
//  then Quicksort is very efficient. On the other hand, if the value of the
//  "Pivot item" is near either the lowest or highest values that are going to
//  be partitioned within any subgroup, that particular round of Quicksort will
//  not do its job of quickly spliting the subgroups into ever smaller sizes.
//
//  The "median of three" portion of the routine is an effort to pick a good
//  "pivot value". If a "pivot value" can be picked so that it exactly splits a
//  subgroup into 2 equal portions, then Quicksort will be as efficient as
//  possible. An effort is made to do this by trying to find a value which is
//  close to the median of the subgroup. This is done by checking the values at
//  the second, last, and middle positions within a subgroup. The middle value
//  of these three is used as the "pivot value" while the two extremes are
//  placed at the two ends of the subgroup.
//
//  The code given here is based on a flier that Robert Sedgewick (author of
//  "Algorithms") handed out "a few years ago" during a 2-semester sequence of
//  "Analysis of Algorithms". (Professor Sedgewick is 2nd from the left in the
//  center photo at http://groups.yahoo.com/group/CSAtrium/)
//
//**************** ********************* ***********************  *****************

void QuickSort(void) {

  int    i, j, k, StackPtr;
  int    LeftEnd, RightEnd, LeftPtr, RightPtr, MidPtr, MinGroup;
  unsigned Pvalue, temp;
  double Time1, Time2;

  puts("\nStarting QuickSort");

  Time1 = (double)clock();                    //  Save time to 0.001 sec.
  Time1 = Time1/(double)CLOCKS_PER_SEC;

  RandNbrs[0] = 0;                            //  Sentinel for sort - used by
                                              //  by the Insertion Sort
                                              //  portion.

    //  Initialize left end, right end, stack pointer,
    //  and minimum size for subgroups.

  LeftEnd = 1;                                //  For the first round, the 2
  RightEnd = Nbr2Sort;                        //  ends will be the whole array
  MinGroup = 65;                              //  Years ago this would be ~18

  if (Nbr2Sort > MinGroup)                    //  Run quicksort until no
    StackPtr = 1;                             //  subgroup remains larger
  else StackPtr = 0;                          //  than "MinGroup" elements.


    //  Start quicksort. First, set the pivot value equal to the median of the
    //  array values at RandNbrs[LeftEnd+1], RandNbrs[(LeftEnd+RightEnd)/2],
    //  and RandNbrs[RightEnd]. The minimum of these 3 is placed at
    //  RandNbrs[LeftEnd+1] while the maximum is placed at RandNbrs[RightEnd].
    //  The value at RandNbrs[LeftEnd] is moved to
    //  RandNbrs[(LeftEnd+RightEnd)/2].

  while (StackPtr) {                          //  Loop until all subgroups
                                              //  are partitioned down to
                                              //  <= "MinGroup" size.
    LeftPtr = LeftEnd + 1;                    //  Ptr to left end.
    RightPtr = RightEnd;                      //  Ptr to right end.
    MidPtr = (LeftEnd + RightEnd)/2;          //  Point to middle

                                              //  Start sort of these 3
    if (RandNbrs[LeftPtr] > RandNbrs[RightPtr]) {
      temp = RandNbrs[LeftPtr];               //  elements
      RandNbrs[LeftPtr] = RandNbrs[RightPtr];
      RandNbrs[RightPtr] = temp;
    }

    if (RandNbrs[MidPtr] > RandNbrs[RightPtr]) {
      Pvalue = RandNbrs[RightPtr];
      RandNbrs[RightPtr] = RandNbrs[MidPtr];
    }
    else if (RandNbrs[MidPtr] < RandNbrs[LeftPtr]) {
      Pvalue = RandNbrs[LeftPtr];
      RandNbrs[LeftPtr] = RandNbrs[MidPtr];
    }
    else Pvalue = RandNbrs[MidPtr];
                                              //  The 3 values are sorted and
                                              //  and the median is in Pvalue
    RandNbrs[MidPtr] = RandNbrs[LeftEnd];     //  Fill in hole with LeftEnd

    //  Start the main loop. Move pointers inward until
    //  we find 2 elements that have to be exchanged.

    while (RandNbrs[++LeftPtr] < Pvalue);     //  Set up pointers
    while (RandNbrs[--RightPtr] > Pvalue);    //  for 1st exchange
    while (LeftPtr < RightPtr) {              //  Make these
      temp = RandNbrs[LeftPtr];               //  statements as
      RandNbrs[LeftPtr] = RandNbrs[RightPtr]; //  efficient as
      RandNbrs[RightPtr] = temp;              //  possible.
      while (RandNbrs[++LeftPtr] < Pvalue);   //  Continue this loop until
      while (RandNbrs[--RightPtr] > Pvalue);  //  the pointers cross.
    }

    RandNbrs[LeftEnd] = RandNbrs[RightPtr];   //  After pointers cross, fill
    RandNbrs[RightPtr] = Pvalue;              //  left end and middle hole.

    //  All values to the left of RandNbrs[RightPtr] are <= Pvalue while all to
    //  the right are >= Pvalue. Next, test the 2 subgroups on either side to
    //  see if they are still larger than the minimum efficient size. If both
    //  are still too large, then place the larger one on the stack and
    //  partition the smaller. If only one needs partitioning, then partition
    //  it, otherwise get the left and right ends of a subgroup stored on the
    //  stack in an earlier operation.

                                              //  Move RightPtr into
    RightPtr--;                               //  unsorted left subgroup

    if (RightPtr < MidPtr) {                  //  If left SubGroup is smaller
      if (RightPtr - LeftEnd > MinGroup) {    //  If both are large then put
        QSleft[StackPtr] = LeftPtr;           //  right side on the stack
        QSright[StackPtr] = RightEnd;         //  and sort the left side.
        RightEnd = RightPtr;
        ++StackPtr;                           //  Ready for next subgroup
      }
      else if (RightEnd - LeftPtr > MinGroup) //  Else if just have to
        LeftEnd = LeftPtr;                    //  sort the right side
      else {                                  //  Else neither gets sorted. Get a
        LeftEnd = QSleft[--StackPtr];         //  prior subgroup from the stack.
        RightEnd = QSright[StackPtr];         //  (Will be garbage if all
      }                                       //  subgroups are sorted)
    }                                         //  End of "if left is smaller"

    else {                                    //  Else left side is larger
      if (RightEnd - LeftPtr > MinGroup) {    //  If both sides are large
        QSleft[StackPtr] = LeftEnd;           //  then put left side on
        QSright[StackPtr] = RightPtr;         //  the stack
        LeftEnd = LeftPtr;                    //  and sort the right side
        ++StackPtr;                           //  Ready for next subgroup
      }
      else if (RightPtr - LeftEnd > MinGroup) //  else if left side is
        RightEnd = RightPtr;                  //  too large, then sort it.
      else {                                  //  Else neither gets sorted. Get a
        LeftEnd = QSleft[--StackPtr];         //  prior subgroup from the stack
        RightEnd = QSright[StackPtr];         //  (Will be garbage if all
      }                                       //  subgroups are sorted).
    }                                         //  End of "if left is larger"
  }                                           //  Repeat until all subgroups are
                                              //  small.

                                              //  Finish up with "Insertion Sort"
  for (i = 2; i <= Nbr2Sort; i++) {
    k = i;
    j = i - 1;
    temp = RandNbrs[k];
    while (RandNbrs[j] > temp) {
      RandNbrs[k] = RandNbrs[j];
      j--;
      k--;
    }
    RandNbrs[k] = temp;
  }

  Time2 = (double)clock();
  Time2 = Time2/(double)CLOCKS_PER_SEC;

  printf("\nThe time to sort %'d items via QuickSort was %g seconds.\n",
    Nbr2Sort, Time2 - Time1);


  PauseMsg();

  puts("\nDo you want to see the random numbers after they were sorted (Y or N)?");
  gets(Databuff);
  if (tolower(Databuff[0]) == 'y') {
    for (i = 1; i <= Nbr2Sort; i++) {
      printf("%4d %'16u\n", i, RandNbrs[i]);
      if (!(i%20))
        PauseMsg();
    }
    PauseMsg();
  }
}




//*************** ******************* ************************* ******************
//
//                                    ShellSort
//
//  If you are only going to learn how one sorting algorithm works, concentrate
//  on Shell Sort. On most arrays that you are ever going to work with it is
//  nearly as fast as Quicksort, and it is much easier to code
//  (and understand).
//
//  Shell Sort is based on Insertion Sort. In fact, if you are working on a
//  very small group of numbers, it is exactly the same as Insertion Sort. If
//  you are sorting a larger group, then it is just an expansion of Insertion
//  Sort. Shell Sort breaks down large arrays into a series of small sections
//  which it then treats as though they were "Insertion Sort".
//
//
//            -------------------------- -------------------------------------
//  RandNbrs | A | B | C | D | A | B | C  | D | A | B | C | D | A | B | C | D |
//            -------------------------- -------------------------------------
//             1   2   3   4   5   6   7    8   9   10  11  12  13  14  15  16
//
//  For example, let's assume you are going to sort 16 elements and are using
//  the 1, 4, 13, etc. sequence for "gap" sizes. The algorithm will first use a
//  "Gap" size of 4. It will run 4 separate simultaneous "Insertion Sorts". One
//  of these will be an "Insertion Sort" on the numbers in the "A" positions.
//  The other 3 "Insertion Sorts" will use the "B", "C", and "D" groups. When
//  the "Gap = 4" process is finished, the array will be roughly sorted with
//  most of the small value numbers concentrated near the low end of the array.
//  Similarly, most of large value numbers will be concentrated near the high
//  end of the array. The algorithm then continues with a "Gap" size of 1. This
//  is essentially an ordinary "Insertion Sort", and "Insertion Sort" is very
//  efficient on arrays that are nearly sorted.
//
//  If the number of elements to be sorted is still larger, then the elements
//  are initially sorted using a "gap" size of 13. This is followed by a "gap"
//  of 4 (as above) and finally a "gap" of 1. Still larger lists that are to be
//  sorted will use larger initial "Gap" sizes, and then gradually decrease the
//  "Gap" size as progress is made.
//
//  The efficiency of Shell Sort can be fine tuned by changing the sequence of
//  "gap" sizes. The 1, 4, 13, 40... series was originally sugested by Knuth.
//  Two other series are better candidates for the gap sizes. The user can
//  experiment with a choice of:
//  1)  1, 3, 7, 21, 48...
//  2)  1, 4, 13, 40...
//  3)  1, 8, 23, 77, 281, 1073...
//
//**************** *********************** *********************** ***************

void ShellSort(void) {

  int choice, i, j, k, GapPtr, Gap;
  unsigned temp;
  double Time1, Time2;

  puts("\nYou may experiment with the gap sizes that are used in Shell Sort");
  puts("\nPick one of the following sequences for the gap size.");
  puts("(Any other number cancels Shell Sort)\n");

  puts("1)  1, 3, 7, 21, 48, 112,...");
  puts("2)  1, 4, 13, 40, 121, 364,...");
  puts("3)  1, 8, 23, 77, 281, 1073,...");

  gets(Databuff);
  choice = atoi(Databuff);

  if (choice == 1) {                    //  Copy one of the three gap sequences
    for (i = 1; i <= 20; i++)
      Gaps[i] = Gaps13[i];
  }
  else if (choice == 2) {
    for (i = 1; i <= 20; i++)
      Gaps[i] = Gaps14[i];
  }
  else if (choice == 3) {
    for (i = 1; i <= 20; i++)
      Gaps[i] = Gaps18[i];
  }
  else return;

  puts("\nStarting Shell Sort");

  Time1 = (double)clock();                        //  Save time to 0.001 sec.
  Time1 = Time1/(double)CLOCKS_PER_SEC;

  temp = Nbr2Sort/3;                              //  Set up GapPtr
  for (GapPtr = 1; Gaps[GapPtr] < temp; GapPtr++);
  GapPtr--;
  Gap = Gaps[GapPtr];

  do {
    for (i = Gap + 1; i <= Nbr2Sort; i++) {
      temp = RandNbrs[i];
      k = i;
      for (j = i - Gap; j > 0; j -= Gap) {
        if (RandNbrs[j] <= temp)
          break;
        RandNbrs[k] = RandNbrs[j];
        k = j;
      }
      RandNbrs[k] = temp;
    }
  } while (Gap = Gaps[--GapPtr]);

  Time2 = (double)clock();
  Time2 = Time2/(double)CLOCKS_PER_SEC;

  printf("\nThe time to sort %'d items via Shell Sort was %g seconds.\n",
    Nbr2Sort, Time2 - Time1);

  PauseMsg();

  puts("\nDo you want to see the random numbers after they were sorted (Y or N)?");
  gets(Databuff);
  if (tolower(Databuff[0]) == 'y') {
    for (i = 1; i <= Nbr2Sort; i++) {
      printf("%4d) %'16u\n", i, RandNbrs[i]);
      if (!(i%20))
        PauseMsg();
    }
    PauseMsg();
  }
}




//*************** ******************** ****************** **************
//
//                    Misc routines
//
//*************** ******************** ****************** **************

void PauseMsg(void) {

  puts("\nPress RETURN to continue.");
  gets(Databuff);
}