This assignment involves developing sorting algorithms that animate the sorting process as they sort. You are required to implement at least three of the sorting algorithms mentioned below, each must be able to display it's progress using either the draw.ss graphics library or the gui.ss library (or use both!).

There are no fixed requirements as to what the animation looks like, other than it should give the user a good idea of how the algorithm works (or at least be useful to a person who knows how the algorithm works). Simply displaying a list of numbers is not very useful...

This is meant to be a significant assignment, and it counts as two homeworks. There are many issues involved that I want you to pay attention to:

• sorting algorithms
• generative recursion
• divide and conquer
• Model/View/Controller (seperate the graphics code from the sorting code as much as possible)
• documentation - this requires non-trivial code, and if you expect us to grade it you MUST provide adequate, consistent documentation.

Insertion Sort

Insertion Sort is described below (pseudo-code):

Given a list of elements L = ( e1 e2 ... en ) with length n.

Create a new list of elements NewL that is initially empty.

For each element ei in L:

      insert ei into the correct place in NewL

      remove ei from L



NewL is now the sorted list.

Note that this algorithm requires that there is some way of inserting an element into an ordered list, this can be done by scanning the new list until the proper place is found and inserting the element. This algorithm has the property that at any time during the execution of the algorithm, the list NewL is always ordered.

For example: given the list '(4 1 8 7 3 2), insertion sort would initially set the new list to empty. The first step would involve putting the number 4 into the correct place in the new list, resulting in a new list of '(4). The second step involves find the right place in the new list to put the number 1, this results in '(1 4), next 8 would be placed in the right place resulting in '(1 4 8), and so on.

Bubble Sort

Bubble Sort is the basic sorting algorithm we have written and played with in class. At each step, the list is scanned from left to right, each pair of adjacent elements are compared and swapped if necessary so that the smaller element is on the left. Scanning the entire list once will result in the largest element being moved all the way to the right end of the list (it has been bubbled to the end). Repeating this once for each element in the list (repeat n times, where n is the size of the list), resulting in a sorted list. Each element has been bubbled to it's correct position. Here is some pseudo-code:

Given a list of elements L = ( e1 e2 ... en ) with length n.


Do n times:
       For i=1 to n-1 (for each element ei in L except the last one.):

             If ei > ei+1 Then swap ei with ei+1

  
The list is now sorted.

You may notice that the above algorithm is excessive on the following way: after the first time through the list, we no longer need to worry about the last element, as it is already the correct value. You might also think about whether the we need to repeat the outer loop n times, or whether fewer times is good enough.

Swap Sort

Swap sort is similar to bubble sort, although the first time through the list the first and second elements are compared (and swapped if necessary), then the 3rd and 4th elements are compared, etc. The second time through the list the first element is skipped and the second and third elements are compared, then the 4th and 5th, and so on...

Given a list of elements L = ( e1 e2 ... en ) with length n.


Do n/2 times:
     For each element ei where i is odd:
             If ei > ei+1 Then swap ei with ei+1


     For each element ei where i is even:
             If ei > ei+1 Then swap ei with ei+1


  
The list is now sorted.

This sorting algorithm is less intuitive than the bubble sort (it's not as obvious why after completion the list will be sorted).

Merge Sort

Merge sort is very different from any of the above sorting algorithims, it sorts by dividing the list in half, sorting each half (recursively) and then merging the results. This is one example of a divide-and-conquer strategy (quicksort is another example).

Given a list of elements L = ( e1 e2 ... en ) with length n.

Divide the list into two lists: 
   Lleft = ( e1 e2   ... en/2) 
   Lright = ( en/2+1 en/2+2   ... en) 

Sort the lists Lleft and Lright.
Merge Lleft and Lright into a single sorted list Lnew.

Lnew is now sorted list.

The above pseudo-code is not complete, there is no mention of how to sort L_left and L_right or how to merge the lists. The sorting of L_left and L_right is done using mergesort (recursively). The merge step requires scanning both lists at the same time, building a new list by adding to the new list the smaller element of the two lists. We actually wrote this function in class.

Quick Sort

We discussed quicksort in class, and we developed a version of it that could handle lists of numbers. (See the lecture notes or the textbook for details on Quicksort

Others ?

For this assignment you will be required to implement quicksort and any two other sorting algorithms - feel free to find other sorting algorithms (you are not limited to those shown above).

You must implement quicksort and any two other sorting algorithms, each must provide an animation of the sorting process. You are free to develop any kind of animation you want, as long as it displays the progress of the sort in a way that can illustrate the differences between the algorithms. In other words, it should be easy to recognize which algorithm is being used by looking at the animation.

The animation shown here is just one possible way of viewing the progress of a sorting algorithm. The algorithm displays the progress of bubblesort on a specific set of inputs (a specific list of numbers). For this animation the screen is updated after each step (each scan of the entire list), it is certainly possible to update after each comparison!

In general, you should try to create code that takes care of the view (the code that draws graphics or modifies GUI elements) without worrying about the specifics of the sorting algorithm. Develop the sorting algorithms without worrying about the animation. The best solutions will include minimal dependency between these two parts of the system, this makes it possible to easily add new algorithms, and easy to modify how the animation looks without changing the code in the sorting algorithms.

Note that if you do a good job of seperating the code, the assignment will be much easier, since adding animations to each sorting algorithm will be very similar.

You can get extra credit of 10 points for including support for keeping track of the total number of comparisons done for each of your sorting algorithms. The idea is that we could then run each algorithm on the same input, and determine which is best (fastest in terms of the number of comparisons required) for that specific input.