CS 3158 -- Design and Analysis of Algorithms

Fall 1998

Animation Assignment 2: Shellsort

Due November 9

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;
       block := block*3 + 1;
   until (block > n);
       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);