CS151 Lab 7:  Sorting It All Out

Due Tuesday, April 3, 2001 at 11:59 PM

In this lab you will implement various sorting algorithms, including a graphical subsystem to help visualize the sorting process.

See Prof. Wong's SIGCSE 2001 materials for more information, documentation and demos.

Merritt Sorting Taxonomy

In her paper "An Inverted Taxonomy of Sorting Algorithms," (Communications of the ACM, Jan. 1985, Vol. 20 No. 1, pp. 96-99), Susan Merritt describes how all binary comparison sorters can be classified  according to how they implement a "divide-and-conquer" technique of splitting and joining.  Merritt claims that all sorters follow the following recursive execution pattern:   

1. Split the array into two sub-arrays.
2. Sort one sub-array.
3. Sort the other sub-array.
4. Join the two sorted sub-arrays back into the orginal size array. 

While Merritt's paper does not describe the process in terms of design patterns, it is a perfect match for the Template design pattern.

Template Pattern for Sorting:

In the Template design pattern , a concrete public method in the abstract class calls abstract non-public methods in a particular sequence to complete a task.   The concrete method is a "template" for the process.   How the actual sub-chores are performed is determined by the concrete sub-classes while the overall process is controlled by the abstract class.   All the sub-classes need to do is to implement the abstract methods called by the template method.   Thus the template method is a invariant behavior which calls variant methods of the sub-classes.   One can think of the concrete classes as providing "services" to the abstract class in a manner very similar to how components of a framework system provide services to the framework.

The abstract sorter, AComparableSorter, has an invariant sorting behavior that manifests itself as a concrete sort() method.   This method has the following steps:

        public void sort( IComparable[] array, int lo, int hi)
        {
             if(lo<hi)   // only sort arrays with 2 or more elements!
             {
                    int s = split(array, lo, hi);
                    sort(array, lo, s-1);
                    sort(array, s, hi);
                    join(array, lo, s, hi);
             }
        }

where split() and join() represent variant behaviors and are thus manifested as abstract methods.

Plan of Attack

Your program should have all the features of the on-line demo except HeapSort and ShakerSort.

Note that some of the classes are supplied for you in the CS151 FTP download site in the Sorter package:  ftp://exciton.cs.oberlin.edu/CS151

Some additional docuementation can be found here.

To orient you as to what is required when:

For week 1:   All the required algorithms must work with an automatically updating text area display.

For week 2:  Full functionality of the on-line demo.  

Remember, get small pieces working one at a time!

Here is a recommended process to get the lab working:

1. First program the ability to create the data to be sorted and to automatically display the contents of the data arary:
   1. Add a Build button that instantiates an array Objects filled with CIntegersin numerical order.    The size of the array should be determined from a text field initialized to a default value.
   2. Add the JTextArea on which to display the data with one value per line.
   3. Print the array after building it. 
   4. Modify the build procedure to build a random array with no repeated values (see Section 1A ):
      1. Fill the array with values which equal their array index.
      2. Go throught the array and swap each element with some randomly chosen other element.
   5. Add the simple animation of the values of the array in the JTextArea.
      1. Add the Timer and ActionListener.
      2. Write the ArrayMapper  and A Command classes.
      3. Use and ArrayMapper and ACommand to display the data array every tick of the Timer.
      4. Be sure to remove the manual update of the text area from the Build button. 
2. Add a Sort button that uses the ASorter to sort the array.
3. Add one radio button: 
   1. Initializes an ASorter variable to a simple concrete sorter that simply prints something during a split or a join. 
   2. Test your system before going on.
4. Make a SelectionSorter and test it.
5. Modify the Sort button to start the sorter on its own thread.
6. Modify the Selection Sorter radio button so that the AOrder object is obtained via a factory method.    This will enable us to dynamically modify (decorate!) the ordering strategy next week. 
7. Add the rest of the sorters.    Note that the new JBuilder has the ability to add the ButtonGroup from the main component palette.   It is a non-visual component, but once you add it, a radio button can be set to use it.   No more adding the button group by hand!
8. You have no chance to sort make your time.

Requirements for this week (Lab 7):

Your program for this week should be able to

1. Construct an array filled with sequential CIntegers but in random order.
2. The number of elements in the array should be adjustable at run time.
3. The sorting should run on its own thread.
4. Sort the array using all the sorters in Section 1.
5. Automatically display the data in a text area.

Requirements for next week (Lab 8):

Essentially, in the end your program should have all the capabilities of the SIGCSE 2001 demo.  Specifically, your program for next week should add the following capabilities:

1. Graphically show the array being sorted.
2. The data should be graphed as either dots or bars (selectable at runtime).
3. Check boxes to enable
   1. The objects being compared to show up as a distinct color and for the sorting to pause for a user definable amount of time.   The compare color should be selectable.
   2. The arrays being split off to change to different colors  and when joined back together, for the color to be returned to the original color (to within round-off errors).   When the array is being split or joined, the sorting should pause for a user definable amount of time.
   3. The number of compares performed during the sort to be displayed.
   4. The number of accesses to the data i.e. number of times getValue() is called, to be displayed.
   5. The order of sorting to be reversed.