Extend stringLinkedListList by adding a sort method, name this new class sortableStringLinkedList. It will be helpful to already have done lab4, but it is not mandatory for this part.
As the name indicates, method sort sorts the list of strings; assume that it does it in ascending order. As you see below, the code for sort is given to you. The actual sort will be performed by the mergeSort method, the other helper method size will return the node-count in our list. No detail explanation of size is given here, but you are responsible to write it.
public void sort() {
if (header_ != null)
header_ = mergeSort(header_,size());
}
mergeSort is recursive and will return a new header which is the header for our linked list after the sorting is complete. The sort process could cause a new node to become the header.
private ListNode mergeSort(ListNode h, int size) {
if (size <= 1) return h; //base case
Write a code segment that splits the list into two lists of
equal size when size is even. Make first reference
the 1st half. Make second reference the 2nd half.
Be careful to NOT allow the end of the sublist referenced by
first to continue to reference second.
When size is odd, the sublist first should naturally
have one fewer node than the nodes in the sublist second.
Keep the following three lines exactly as they are
first = mergeSort(first,size/2); //apply mergeSort to the 1st half
second= mergeSort(second,(size+1)/2); //apply mergeSort to the 2nd half
return merge(first,second); //merge to halfs together
}
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 ListNode merge (ListNode first, ListNode second) {
ListNode combined;
Make combined reference either the 1st node in
first or the 1st node in second depending
on which has a smaller string. Also, advance in the appropriate
sublist (i.e. first = first.next_; or second=second.next_;)
ListNode temp=combined;
while (first !=null && second != null) {
set temp.next_ to 1st node in first or the 1st node
in second depending on which has a smaller string.
Again, advance in the appropriate sublist.
Advance temp.
}
if (first !=null)
temp.next_ =first;
else
temp.next_=second;
return combined;
}
Use the testSortable.java to test your sortableStringLinkedList class.
write another test program; follow the logic below:
mail me the sortableStringLinkedList.java file as well as a copy of the test program that you were instructed to write.
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 Merge sort).
This applet will need a sortableStringLinkedList field. 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. The appropriate range for Max Count is 0..5000; if the user specifies a value that is not in range, set it to 5000 using the setText method.
The Elapsed Time text field is designed to help us compare how long it takes to utilize the two different sorting techniques.
When the New Sorted List (Merge) button is hit, a list is created with Max Count randomly generated elements in it (the integer stored in Max Count will be needed here). The Iterator in this case should be a stringLinkedListItr. Once all elements are inserted, the list's merge method should be called to sort them. long time=System.currentTimeMillis(); will store the current system time in Milliseconds in a Long variable time. Store the current time before generating, storing, and sorting the numbers. The difference between time stored before the processing begins and current time when it is completed is the elapsed time. This will the time displayed in the Elapsed Time text field.
When the New Sorted List (Insertion) button is hit, a list is created with Max Count (TextField) randomly generated elements in it. The Iterator in this case should be a stringLinkedListSortedItr. This time, all values are inserted in the right order and we don't need a call to sort. Again, currentTimeMillis(); can be used to determine the elapsed time.
Use the String Rand() method below to generate the elements; simply, include it in your applet and use it when generating the random stings. You had utilized a similar strategy in the test program for part 1.
//generate a string containing a 3 digit random number between lowRange and
//highRange. Note 45 will appear as "045", and 450 will appear as
//"450". lowRange and highRange should be declared as static final in the
//applet with 10 and 500 respectively.
public static String rand () {
int r = lowRange + (int)(Math.random()*highRange);
if (r < 100) return "0"+String.valueOf(r);
return String.valueOf(r);
}
The paint method in this applet should be straight forward. create an iterator for our list and for each element in it draw a line with the length specified. The y value should simply start at 100 and increase until all values are retrieved. drawLine from the graphics class is what you use to draw your lines.
mail me the sortApplet.java file. Also, go through
the following process and email me the answer to the questions that
I pose at the end.
At what point, with certainty, could you say that merge sort begins to outperform Insertion sort?
What were the values that you attempted for count? Explain what made you draw your conclusion?