The purpose of this program is to demonstrate how the quicksort algorithm behaves. You will be implementing quicksort, but in a way that allows the program's user to visually observe how the algorithm proceeds by watching animated colored bars.
Two base classes (DoubleCell and SortGUI) are provided to assist with the basics of animation. You should not alter these classes, but write a Driver class that uses the provided classes to implement a proper quicksort.
The SortGUI class provides a GUI that implements buttons for the user to start and stop a sort animation, as well as buttons to reset the sort data in either random, ascending or descending order. These data are displayed for the user as rectangular bars on a JFrame. Programmatically, your code accesses each bar by virtue of a doubly-linked list. The form of a list cell is defined by the DoubleCell interface. You will need to use the methods of DoubleCell to manipulate the list. Also, the list includes sentinel cells at both ends. The getAnchor() and getBackAnchor() methods from SortGUI provide access to the anchors, that in turn link to the sentinel cells.
SortGUI interacts with your Driver class in two ways. Firstly, SortGUI calls a Driver method, named initializeSort() every time that the user chooses a new set of data. Your Driver needs to implement initializeSort() as a public parameterless void method that performs whatever function that you find necessary to reset for a new sort. The second obligatory method in Driver is called sortNext(). This method is called repeatedly by SortGUI to accomplish a sort. In other words SortGUI uses a Timer object to generate timed events. Each timed event results in another call to sortNext(). Your task is to cause each sortNext() call to perform one more step of the sort. One step would be something like selecting the next pivot or advancing the lower pointer of the pivot range by one or advancing the upper range pointer by one position or swapping two values within the pivot range. At all times your code should keep the current pivot bar colored in red and the two range bars colored green so the user can better follow the animation.
Your sortNext() method is also responsible for terminating the sort at the proper time. A stopSorting() method is included in SortGUI for your code to call when it is time to end the animation.
Write a second complete program that implements the merge sort algorithm in the same way. That is this program must provide a good step-by-step animation of merge sort using SortGUI and DoubleCell.