|
|
Can I use a doubly linked list? No, only one link per node is allowed.
Can I store the input in reverse order? Yes, but your output should still be the same as if it were stored in sorted order.
Can I bubblesort "backwards" (i.e. move the largest to the right instead of the smallest to the left) No, you should bubblesort in the normal way so that your intermediate passes match the example output.
Can I use recursion to print out my linked list in reverse order? Sure. Since you only perform the printing for very small values of N, this will not affect the asymptotic running time or space usage.
Can I swap keys with code like temp = x->key; x->key = y->key; y->key = temp; No. This is what is meant by "rearranging keys." You are only permitted to rearrange links.
Can I allocate an array of size h for scratch space? You will lose some points for using excessive space.
What counts as a comparison? The number of times you compare one key to another key. Don't count comparisons like i < N in loop control.
What exactly is one pass of bubble h-sort? One pass in the array implementation looks like:
for (i = N - 1; i >= h; i--)
if (a[i] < a[i-h]) {
temp = a[i];
a[i] = a[i-h];
a[i-h] = temp;
}
How fast should my algorithm be? Using Knuth's increment sequence, the worst case running time is proportional to N^(3/2). (See Sedgewick, Property 6.9.) So, if you're running time is quadratic (even on degenerate inputs), you are doing something wrong and should try to figure out what is slowing down your code. Note that the N^(3/2) bound is for the worst case: you should expect your program to run faster in practice.
How do I measure the running time of my program in seconds from Unix or OS X? Use the command:
and look out the output for user time. Note that you should use the full path name; otherwise your shell might use its own built-in time command. Also, /usr/bin/time may not work if you use piping./usr/bin/time a.out < input1000000.txt
How do I measure the running time of my program in seconds from Windows? The easiest solution is to use a stopwatch. A more complicated approach involves adding in some C code as in timing.c. Srivas Prasad '03 suggests chaing the command prompt to display the time using "prompt $t", creating a batch file with "cls" and "linksort.exe < input.txt > output.txt". The clear screen command clears the screen and displays the starting time in the prompt; upon termination the prompt shows the ending time.
|
|
Input. Your program should read in a sequence of integers separated by whitespace from standard input. It should not matter whether the integers are separated by a single space, multiple spaces, or newlines. Here are some sample input files. You may also use generator.c to generate random test instances. This program uses the Mersenne twister pseudo-random number generator.
Output. Your program should produce nicely formatted output as described in the assignment. Our output is generated using
printf("%8d %5d %9d %9d", h, pass, cmp, exch);
Reference solutions. As a special bonus this week, we provide our source code for the array implementation of shellsort. You can use this to check your output, and also to glean some information about our implementation.
|
|
Besides providing details about your implementation which are not clear from the comments within your source code, your readme.txt file should also contain:
|
|
These are purely suggestions for how you might make progress. You do not have to follow these steps.