You are going to complete sortableIntList by writing its sort() and merge() methods.
Obviously, lab4 is expected to have already been completed before you begin writing the last two methods defined here. The purpose of sortableIntList is to allow our list to be sorted through the invokation of the sort method.
sort is naturally recursive and will return a new sortableIntList with all the same nodes as the original except that they will be sorted. This method uses the half() method to split the list into two sublist that are sortableIntList objects, then sort each and use the merge() method to build a new list from those sorted halves and return this new list.
public sortableIntList sort( ){
if (size is 1) return this; //base case
invoke half() bind its result with a variable second.
sortableIntList first = sort();//Sort the first half
second= second.sort();//Sort the 2nd half
return merge(first,second); //merge two halfs together and return result
}
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:
sortableIntList merge (sortableIntList fir, sortableIntList sec) {
sortableIntList m=new sortableIntList();//create a new list
try{
//make sure the iterator (current_) for both fir and sec is at the beginning
//of their respective lists.
if the first element in fir is less than first element in sec {
insert the first element in fir into m
advance iterator in fir
}
else {
insert the first element in sec into m
advance iterator in sec
}
while (current is valid in fir and current is valid in sec) {
if the current element in fir is less than current element in sec {
insert the current element in fir into m
advance iterator in fir
}
else {
insert the current element in sec into m
advance iterator in sec
}
}
if (current is valid in fir)
m.current_.next_=fir.current_;//append the rest of fir to the end of m.
else
m.current_.next_=sec.current_;//append the rest of sec to the end of m.
}
catch (Exception e){System.err.println("error in merge");}
return m;
}
Use the sorttest2.java to test your sortableIntList class.
create a variation of test2.java to test sorting of a larger list.
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 MergeSOrt 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.
mail me the sortableIntList.java file and your sortApplet.java files.