CS 1713 Section 1 Spring 2011, Homework 5

Animated Sorting Algorithms

The following files have been provided for you:

• SortAnimation.java. This class contains the code that will drive your sorting algorithms. It has a main method that accepts a command-line parameter naming the sorting algorithm as one of the following: bubble, selection, insertion, quicksort. The program will make an object of one of the subclasses of AnimatedSort that you have written, then use that object to sort some random numbers. Your algorithm will call back to the drawArray method in SortAnimation to provide points for the program to draw the partially sorted array.
• AnimatedSort.java. This abstract class should be extended by your sorting algorithms, allowing SortAnimation to make objects in a consistent way.
• AnimatedBubbleSort.java. This class gets you started by providing you with the bubble sort algorithm as a subclass of AnimatedSort.

• AnimatedSelectionSort.java, the selection sort algorithm. Have the algorithm call back to drawArray() after each swap.
• AnimatedInsertionSort.java, the insertion sort algorithm. Have the algorithm call back to drawArray() after each insertion.
• AnimatedQuickSort.java, the quicksort sorting algorithm. Have the algorithm call back to drawArray() at the beginning of each recursive call.

How To Do This Assignment

Once you have written non-functional versions of the other sorting algorithms, test the program by running it for bubble sort. See how bubble sort behaves on the screen. To stop the program, just press CTRL-C or kill it by clicking on the X provided for that purpose by the window system.

Selection sort is the easiest one to code, so start with that one next. Observe how differently selection sort works, even though the resulting sorted order is the same.

Insertion sort should come next; it also behaves differently.

Quicksort comes last. Quicksort is recursive, making it a little harder to code. You may use a version of quicksort you find on the Internet if you like as long as you cite the source in your comments. Quicksort is far more efficient than the other algorithms, but since we are drawing the result of every recursive call rather than the result of updating the entire array once, it might take longer to animate. Observe how differently it works from the other algorithms.

This assignment is a little different from the others. It has the same pedagogic value as others, e.g. you will have to practice using an abstract class, you will have to code sorting algorithms, etc., but I want you to also think of it as an opportunity for exploration. What happens if you draw the array at points other than the ones suggested? If you e.g. draw the array at every swap, the program will run much more slowly, but you will get to see much more detailed operation of the sorting algorithm. What if you have the array sorted backwards? What does that look like? What if you change the number of elements in the randomly-generated array? What if you allow duplicates in the array? Play with the program a little before you write up the final version that conforms to the requirements set out in this document.

What To Turn In

This program is due at 11:59pm, Monday, March 28, 2011. Late assignments will not be accepted. If you're not done with some part before it's due, turn in what you have for partial credit. Don't cheat.