CSC 241- Assignment 3 (Due April 21, 2003)

• Implement the quick sort algorithm.
• Use sortableIntList in an applet.

Part1-Implement Quick Sort

Extend intList to create a new class sortableIntList. This class inherits all methods of intList as they already exist and adds on a new method named sort that uses the quick sort algorithm to sort the list in ascending order.

As you know, quick sort identifies a pivot value from the elements in a list, then, it moves the values smaller than the pivot to its left and the rest of the values to its right. The left and right sublists are then each sorted by applying the same algorithm to them.

In writing the sort method, you will implement quicksort. Unlike the implementation of quicksort for an array where elements get to move within the same array, here, we can create our left and right sublists as sortableIntLists and when moving value to the left of pivot, to us, it would mean that we are adding those elements to the left sublist and, of course, the other values to the right sublist. Here is the basic algorithm that you need to implement for the sort method:

• If header_ is null or header_.next_ is null, we can assume that no sorting needs to be done for our list (i.e. there is zero or 1 element in the list) and we can just return. Conceptually, this is our base case.
• Construct two sortableIntLists objects, leftSublist and rightSublist.
• We need to identify the first element in the list as the pivot value.
• Iterating through the remaining elements, putting all elements larger in rightSublist and the rest in leftSublist. Keep in mind, the first time you add an element to either of these sublists, you need to use the insertAtBeginning method. So, it may be best to use this method for all insertions as the order in which you insert into sublists has no bearing on the sort process.
• call the sort method of both of these sublists, in effect, sorting them both.
• Consolidate the two sublists as well as the pivot value.
  1. if leftSublist is empty
     1. set header_ to the node with pivot and link it to the header_ of the rightSubtree.
  2. else
     1. Our header_ should reference the same node that the header_ of our leftSublist references
     2. Locate the last node in the leftSublist and link it to the pivot node. Then link the pivot node to the node referenced by the header_ of the rightSublist.
• The list is now sorted.

  Write a test program similar to what you had before for lab4. Construct a sortableIntList and put values in it. Then, display the result of the dump method before issuing a call to the sort method and again after, to show that the sort worked. Be aware that while debugging, you can always use the dump method of the leftSublist or the rightSublist to see the transformation of your sublists before and after the calls to their sort method in the sort method itself.

  What to Turn In

  mail me the sortableIntList.java file.

  ---

  Part2-Implement Sort Applet

  Develop a Sort Lines Applet which has been inspired by Sort Applet Demo made available at javasoft. Notice that the Applet that you will develop won't have the multi-threading requirements that the demo from javasoft does.

  This applet will need a sortableIntList field (l_) . You also need the buttons and text fields that you see in my version. Putting them all in one panel and putting them on top will be a good idea.

  One of our text fields is Max Count which identifies how many data values need to be generated. The default value, what you set Max Count to at the start, is 500.

  When the Generate A New List button is hit; construct a new sortableIntList and bind it with l_. Then, based on Max Count randomly generated numbers and insert them into l_. The appropriate range for Max Count is 0..5000; if the user specifies a value that is not in range, set it back to 500 using the setText method before using the textField. Write a random() similar to the one in test2. This is the method you will use to generate the random numbers.

  When the Apply Sort button is hit; call the sort method for l_.

  The paint method in this applet should be straight forward. You should already know how to traverse a list, it'll just be a mater of displaying lines based on the elements in either l_. Each number should be retrieved and used as the length of a line. The y coordinate of each line should begin at 100 and incremented for each value retrieved from the list. drawLine from the graphics class is what you use to draw your lines.

  ---

  What to Turn In

  mail me the sortableIntList.java file and your sortApplet.java files.