Step 1. First, implement a routine to build a list: read integers from standard input, and 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 print out the contents of the linked list.
Step 2. 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 sorted order. This is not the same as rearranging keys within nodes: that is to be avoided because, in real applications, 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.
Step 3. Next, implement a bubble h-sort. You will need to discover an efficient way to do this, even for large h. Make sure that one pass of your bubble h-sort uses at most a constant amount of auxiliary space and runs in time linear in the input size N. Note that h does not count as a constant - this is too much. However, in general, your bubble h-sort routine will still need more than a constant number of passes to produce a file that is h-sorted. You should think about how you are going to solve this problem before sitting down to write the code.
Step 4. Finally, write a Shellsort variant that uses your bubble h-sort. Use Knuth's increment sequence (1, 4, 13, 40, ...) as in Sedgewick, Program 6.5.
Analysis. Use explicit counters to determine how many key comparisons and exchanges are used. Report these counts and the amount of time your program takes to sort random input files of size 100, 1,000, 10,000, 100,000 and 1,000,000. Include in your readme.txt a two-dimensional table with a row corresponding to each file size and columns giving the total number of comparisons and exchanges used. Also, include a column that indicates how many seconds your program takes on each input.
Input and output.
The input consists of integers separated by whitespace. You may use the
following
sample input files to test your program.
Your program should output the intermediate stages of the sort
for debugging and to provide evidence that your program works.
For example,
on the input file
random10.txt, your program should output:
If N is larger than 20, for brevity
only print out the number of comparisons and
exchanges for each value of h.
a.out < random10.txt
h pass cmp exch 18 79 46 75 99 91 98 53 10 23
----------------------------------
4 1 10 23 46 53 18 79 98 75 99 91
4 2 12 5 10 23 46 53 18 79 98 75 99 91
1 1 10 18 23 46 53 75 79 98 91 99
1 2 10 18 23 46 53 75 79 91 98 99
1 3 27 7 10 18 23 46 53 75 79 91 98 99
----------------------------------
Total 5 39 12
Extra Credit A.
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.
a.out < random100000.txt
h pass cmp exch
----------------------------------
88573 2 22854 5722
29524 4 281904 49788
9841 10 901590 94555
3280 16 1547520 148293
1093 21 2077047 203626
364 29 2889444 274828
121 36 3595644 391385
40 49 4898040 584519
13 46 4599402 634147
4 28 2799888 388543
1 16 1599984 175669
----------------------------------
Total 257 25213317 2951075
Extra Credit B. Design an increment sequence that consistently outperforms the sequences described in the text. Justify your method with numerical experiments.