CSC 241- Assignment 3 (Due November 21st 1997)

• Add a sort method to intList. It will be helpful to already have done lab4 before this assignment. In that lab you added a size field to intList that will be used here. As the name indicates this method sorts the list of integers. However, it doesn't do this on its own. When the sort method is invoked you must then invoke a recursive merge sort method that is private and takes the head of the list and the size of the list as parameters.

  This recursive sort method will return a new head which is the head of the list after the sorting is complete (i.e. in your sort routine, you should be able say something like: head=mergeSort(head,size);). Such a technique where a variable, such as, head need to be sent to a method like mergeSort, but, the method is expected to return a new head is very common in languages like Java. This also means that if you recursively call mergeSort, you will need to employ the same technique for the heads of the sublists as they may change also. Here is the algorithm to follow:

  
        private Node mergeSort(Node head, int size) {
           if (size <= 1) return head;
           make a sublist "first" with one half of the nodes 
           make a sublist "second" with the rest of the nodes 
          first = mergeSort(first,size/2);
          second=mergeSort(second,(size+1)/2);
          return merge(first,second);
        }
        

  As you can see, you will need to develop a merge method that merges the two sublists once they are sorted. Here is the algorithm to follow:

  
        private Node merge (Node first, Node second) {
           if (first == null) return second;
           if (second == null) return first;
  
           Make a list "combined".  move the one node with the larger of
           the two values at the beginning of "first" or "second" into the new
           list.  Note, the node chosen here should no longer be in either
           first or second.
  
           while (first !=null && second != null) {
               append the node with the larger of the two values at the
               beginning "first" and "second" to combined.  Note, the
               node chosen here should no longer be in either first or second
           }
           if (first !=null) append the rest of first to combined
           if (second !=null) append the rest of second to combined
  
           return combined;
        }
        

• Test the sort method by writing a test program. This test program must append 100 randomly generated integer numbers in the range of 10 to 300 to the list, invoke the dump method, invoke the sort method, and again invoke the dump method. You will need to import the class java.lang.Math. This class has a random () method which you can use to generate random numbers between 0 and 1. To demonstrate the use of random (), I wrote test3.java .

• 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 had, however, it is still a neat little applet!
  

  The best approach to implementing this applet to create an intList object that would hold integer values and let the applet draw the lines. The idea is simple, you start with a default set of values, say 20 randomly chosen integers. Draw lines based on those values. Also, show those values at the bottom of the screen in a text area (I used the dump method from intList). When the user clicks on a Sort List button, your applet sorts the list and redraws the lines, also dumping the sorted list at the bottom. Each time user clicks on a New List button, a new set of values is generated that you again draw lines for and dump at the bottom. The Max Count is made to be changeable, but you can't allow too many lines,I think, I picked 80 as my max.

  Checkout Tank Applet2 written by my independent study student David Fleming for some hints on user interfaces.