Durango Bill’s
“C” Program to implement Sort Algorithms
(Source Code)
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);
}