In this assignment, you will implement the Shellsort algorithm using a programming language of your choice, then you will build an animation of the algorithm using the Samba tool from the first assignment. By interspersing output statements throughout your program at key points, you will generate a trace file that will serve as the input to Samba. You should try to make the animation as informative as possible. Its purpose is to convey the algorithm's operations, use of data, behavior, and methodology. Think of using your animation to help explain how the algorithm works to someone who has never encountered the algorithm before. You will be graded on the correctness of the animation (does it accurately reflect the operation of the algorithm), its informative content (does it really help explain what the algorithm is doing), and its general originality and visual aesthetics. Don't just reuse a simplistic animation that you may have seen before.
I will be supplying a few sample data sets for your animation to run
on. The input format will be one integer designating the size of the
input array, followed by that number of trailing integers. Make sure
that your animation can properly handle varying input set sizes.
Additionally, shortly before the assignment is due, I will post one
special input set that you should use as the input to your program for
generating the trace file to be turned in. All you need to do to
submit your assignment is to use the 3158in program to
electronically submit the ASCII trace file of the Samba commands
for that special input set.
Pseudo-code for the Shellsort algorithm is below:
Read in array size (n) and array elements (a[])
block := 1;
repeat
block := block*3 + 1;
until (block > n);
repeat
block := block div 3;
for i := block+1 to n do
val := a[i];
j := i;
while (a[j-block] > val) {
a[j] := a[j-block];
j := j - block;
if (j <= block) goto 333;
333: a[j] := val;
until (block = 1);