Write C programs for selection sort, insertion sort, bubble sort, and a variant of Shellsort, but using a linked-list representation instead of the array-based sort used in class.
First, implement a routine to build a list: read characters separated by spaces from standard input, build a list node for each item consisting of a character and a link to the node for the next character. 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 the sorting routines: they should take as input a link to the beginning of a list, and should either rearrange the nodes of the list or rearrange the keys within the nodes so that the nodes in the list after the sort are in numerical order of their keys. Normally, one would think twice about rearranging keys within nodes, not the nodes themselves, because, in an application, other information would be associated with the keys. However, this assignment is not an application, but a programming exercise, where one of your tasks is to determine which mode of rearrangement is easier and/or more efficient for each algorithm.
Although each of the sorting routines essentially proceeds sequentially through the list, the rather severe constraints imposed by the singly-linked list organization presents special problems for each. Your task is to overcome these constraints and develop simple, elegant implementations of each of the four algorithms without sacrificing efficiency. 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.
With the exception of Shellsort, your algorithms should do the same sequence of key comparisons for any input as the array-based implementations given in the text, or you should justify any differences. For Shellsort, this may be difficult to do without using excessive extra time or space for bookkeeping; find the fastest version that you can. Your goal should be a method with a worst-case running time within a constant factor of the array-based Shellsort for the same increment sequence.
Use your output routine to print out intermediate stages of the sorts, for debugging and to provide evidence that your programs work. Keep your output simple. Run each program on the keys A S O R T I N G E X A M P L E.
Use profiling or explicit counters to determine how many links are followed by each routine. Run each routine on an arbitrarily ordered file of 100 elements. Give a 4 by 2 table with the actual number of links followed by each routine for this experiment along with your estimate of what it should be for $N$ randomly ordered input elements, as a function of N.