CSC 241- Assignment 3

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

Part1-Implement Quick Sort (Due November 21, 2003)

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 (Due 12/5/03)

  Part2.1--intListObserver

  this class should reside in your intList directory and packaged appropriately.

  intListObserver is going to follow the pattern from parkingLotObserver from assignment#2-part1.

  intListObserver extends Canvas as the observer for parkingLot did.

  You obviously need an intList field identifying the object that needs to be observed. When constructed, the observer is sent the intList object; this object is depicted graphically by the observer. You need the setSize() method that ensures the observer is large enough in the constructor:
  setSize(1001,1001); should be adequate.

  Write a changeIntList () method that has an intList parameter and binds the intList field in the observer with this new intList object. In This project, we need the ability to observe a newly created intList; this method accommodates that.

  You will also need a paint () method where lines are drawn representing the values in the intList object. writing this method for the observer should be straight forward.

  First of all, you don't need to do anything unless your intList object has elements.

  You should already know how to iterate an intList; your job is to display lines based on the elements you retrieve from it. Each number retrieved is used as the length of a line.

  drawLine(x1,y1,x2,y2) from the graphics class is what you need to use for drawing each line (i.e. g.drawLine(...)). x1/y1 are the coordinates where the line originates and x2/y2 determine the end point of the line. The y1 and y2 are 1 for the first line retrieved and get incremented for each subsequent value retrieved from the list. The x1 should be 1 for all lines drawn and x2 is 1+the value retrived from the list.

  This class will be tested when you complete the applet.

  ---

  Part2.2--sortLinesApplet

  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 needs to be placed in your Applets directory and packaged approprately.

  This applet will need a sortableIntList field (l_) as well as a intListObserver field (o_); they both need to be instantiate when the applet is constructed with l_ being left empty. You also need the buttons and the text field that you see in my version. The buttons and the text field should be placed on a panel and the panel placed at the North boundary of the applet.

  our text field 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:

  1. Construct a new sortableIntList and bind it with l_.
  2. Let o_ know that its intList has changed.
  3. Assume that the appropriate range for Max Count is 0..1000. If the user specifies a value that is not in range, the Max Count field needs to be set back to "500" using its setText() method.
  4. Use Max Count to determine how many randomly generated numbers need to be inserted into your intList object. When you use a getText() method on a textField, you get a String object back. In order for a String object to be useful to you, it must be converted into an int. In the following example, the string x is a String that need to be converted to an int and stored in i:
     int i = (Integer.valueOf(x)).intValue();
  5. Using insertAtBeginning store the right number of randomly generated values in l. The following random() method should be placed in your applet and used when you need to generate random numbers:

               //Generate a random number between 1 and 100
     
               static public int random(){ 
     
                  return 1 + (int)(Math.random()*(float)(1000));
     
               }
     
             

  6. issue a repaint for o_.

  When the Apply Sort button is hit; call the sort method for l_. and again issue a repaint for o_.

  What to Turn In

  mail me the intListObserver.java and sortLinesApplet.java files.

  ---