The rather severe constraints imposed by the singly-linked list organization presents special problems for implementing Shellsort. Your task is to overcome these constraints and develop a simple, elegant implementation that does not sacrifice efficiency.
First, implement a routine to build a list: read integers or characters separated by white space, build a list node for each item consisting of an integer key and a link to the node for the next item. Also, write a routine to write out a list of keys in the order they appear in the nodes, keys separated by spaces.
Next, implement bubble sort: it should take as input a link to the beginning of a list, and should rearrange the nodes of the list so that they are in numerical order of their keys. Important: This is not the same as rearranging keys within nodes: that is to be avoided because, in an application, other information might be associated with the keys, or other data structures might have pointers to the nodes. You may use dummy nodes or circular lists as you see fit, but do not use doubly-linked lists. That is, you should use only one link per node, with a constant extra number of links for bookkeeping.
Next, implement a bubble h-sort. The first problem that you need to solve for this assignment is to find an efficient way to do this, even for large h. Using a table of size h or time proportional to more than a constant factor time N would not be considered efficient. You should think about how you are going to solve this problem before sitting down to write the code.
Finally, write a Shellsort variant that uses your bubble h-sort. Debug with the increments 13, 4, 1 and the keys A S O R T I N G E X A M P L E for comparison with the diagrams in the book. Use your output routine to print out intermediate stages of the sort, for debugging and to provide evidence that your programs work. Keep your output simple and short.
The second problem that you need to solve for this assignment is to find an effective increment sequence for large N. Here you need to mix an intuitive feel for what is needed with any creative (or half-baked) ideas that you might have, then design and execute some experiments to help in your search for some good sequences.
Use profiling or explicit counters to determine how many comparisons are used. Run your program on random files of 100, 1000, 10000, ... floats, stopping when a file takes more than a second to sort You don't need to precisely track the time: just stop when it gets slow. Include in your readme a two-dimensional table with a row corresponding to each file size and a column corresponding to each increment, giving the number of comparisons used on each pass.
Extra Credit. The method is much more effective if you alternate directions in passes through the list. Make your program change the direction of all the links on the way through the list, so that it goes the other direction on the next pass. Find a good increment sequence for that variant.