CSC 241- Assignment 3

• Implement the quick sort algorithm.
• Compare insertion sort (Lab4) and quick sort performance by writing an applet.

Part1-Implement Quick Sort (Due April 20, 2001)

Extend intList to create a new class sortableIntList. This class adds a public method to intList 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 April 27, 2001)

  Develop a Sort 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.

  The applet that you will develop should also help in finding empirical data about the time complexity of the two algorithms deployed here (Insertion sort and quicksort).

  This applet will need an intList field (l_). You also need the buttons and the text fields that you see in my version. Put the buttons and the text fields in one panel and place the panel at the North border.

  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. The appropriate range for Max Count is 1..5000; if the user specifies a value that is not in range, set it back to 500 using the setText method.

  The Elapsed Time text field is designed to help us compare how long it takes to generate and sort elements.

  Here is what you need to do in your actionPerformed method:

  • When the New List (QuickSort) is clicked:
    1. Bind l_ to a new sortableIntList object.
    2. long time=System.currentTimeMillis(); will store the current system time in Milliseconds in a Long variable time.
    3. Use insertAtBeginning to add Max Count randomly generated numbers to l_.
    4. Call sort in l_ to sort it.
    5. determine the elapsed time and display it in the designated text field. The difference between time stored before the processing begins and current time when it is completed is the elapsed time.
  • When the New List (InsertionSort) button is hit:
    1. Bind l_ to a new orderedIntList object.
    2. long time=System.currentTimeMillis();
    3. Use insert to add Max Count randomly generated numbers to l_.
    4. determine the elapsed time and display it in the designated text field.
  • Be sure to issue a repaint before returning.

  include a method random() similar to the one in test2 (used for testing intList). This is the method you will use to generate the random numbers during the insertion process. 10 to 500 is a reasonable range of values generated.

  The paint method in this applet should be straight forward. You should already know how to traverse a list by using the iterator methods. Here, you will display a line based on each value retrieved from l_. The drawLine method for Graphics objects require four arguments, the X and Y coordinates of the two end points. The Y-coordinate for the end points of the first line drawn is 100, below the panel displayed on top. The Y-coordinate of each subsequent line drawn needs to be incremented by one. X-coordinate of the left end point should be 1 for all lines drawn. The X-coordinate of the right end point should be the value retrieved from l_. For more details, click on drawLine from the Graphics class.

  Once you are satisfied that the applet works correctly, go through the following process to compare the performance of the two sorting techniques.

  • Set Max Count to 10. Use both New List (InsertionSort) and New List (QuickSort) to generate and sort the 10 numbers and draw them. Record the time it took to perform InsertionSort and the time it took to perform QuickSort.
  • Retry and record the average elapsed time for a total of 5 trials of each sorting technique.
  • Steadyly increase count and go through this process for each new count until you have tried the upper limit that we have chosen here, which is 5000; initially, using small increments and then going to larger increments as you pass 100 and then 1000 max counts.

  What to Turn In

  mail me the sortApplet.java file and add a link to your 241 page for this applet.

  Include the following in your email:

  1. A table showing the Max Counts you tried along with the average elapsed times recorded in each case.

  2. The answer to following question: At what point, if at all, could you say that quicksort begins to outperform Insertion sort?