CPSC 124 (Winter 1998): Lab 9
Sorting and Layout Managers
FOR THE NINTH LAB in Computer Science 124, You'll be starting with something a little different. Instead of writing your own applet, you will working with an existing applet to help you learn about sorting. In the second part of the lab, you will learn more about GUI components and how they can be laid out in an applet.
For this lab, you will only need one folder from the cpsc124 folder on the network. Copy the "GUI Stats Starter" folder into the java folder on your M drive.
The exercises at the end of the lab are due in class on the Monday following the lab.
Outline of the Lab
Sorting with xSortLab
For the first part of the lab, you will use an applet called xSortLab, which I originally wrote for use in Computer Science 100. It is meant to help students learn about various sorting algorithms. The applet can be found on a separate page, which also has more detailed information than I will give here about how to use the applet. In the lab, you will be experimenting with several different sorting methods. The experiments should convince you that different algorithms can take remarkably different amounts of time to accomplish the same goal.
When the xSortLab applet starts up, it shows an array of sixteen bars of various lengths. This applet can sort these bars using any of five sorting methods. The available methods are listed in a pop-up menu near the upper right corner of the applet. Use this menu to select "Insertion Sort," which we have talked about in class. Click on the Step button, and the applet will perform one step in the sort. If you click the Go button, the applet will keep performing steps automatically until you stop it or until the sort is complete. A short description of each step is displayed at the bottom of the applet. (If you want to have time to read them, use the Step button.)
Although we have talked about insertion sort in class, to really understand how it works you have to see it in action. Play with the applet until you feel that you understand insertion sort well enough to do it by hand. One of the exercises asks you to show how insertion sort works on an array of integers.
When you are finished with Insertion Sort, switch the sorting method to "Merge Sort". Step through the sort using the "Step" button. Your objective is to understand the sorting algorithm in some detail, so you can write about it and show how it would operate on a given array. It's also a good idea to watch the sorting procedure run automatically at the fast speed. Make sure that you spend enough time to really understand how merge sort works.
Timing Sorts with xSortLab
In addition to "visually" sorting an array of bars, the xSortLab applet can invisibly sort an array of integers and time how long it takes. To work with this mode of the applet, select "Timed Sort" from the pop-up menu at the very top of the applet.
You'll see a pop-up menu at the bottom of the applet for selecting a sorting method. At the top of the screen are two text-input boxes. The first box lets you specify the array size. The second box lets you specify the number of arrays that will be sorted. This is necessary if you want to sort small arrays, since the computer sorts them too quickly to measure the time accurately. The trick is to sort a whole bunch of arrays and divide the total sorting time by the number of arrays to get the sorting time for one array.
Try sorting a single array of 10000 items using both Insertion Sort and Merge Sort. (Note: If you are using a slow computer, you might want to cut down on the number of items here and in the remainder of this exercise.) Write down the time it takes for each method. You only need the "Approximate Compute Time." You can ignore the rest of the information that is displayed in the applet.
Now, try sorting arrays of size 1000 with both methods. Your objective is to find the time that it takes for each method to sort a single array of 1000 items. However, to do this, you will have to sort a bunch of arrays (about 100) and divide the total time by the number of arrays.
Try a few other array sizes. You can collect data for an array size of 5000. You can try Merge Sort on arrays of size 100,000 and even 1,000,000. You might have time to try Insertion sort for 100,000 items, but don't try using it for 1,000,000 items!
You will use the data you collect for one of the exercises at the end of the lab.
Simple Stats in a GUI
In an earlier lab, you worked with a program that would take a set of numbers entered by the user and compute some statistics. It was an "old-fashioned," console-based program. In this lab, you'll work with an applet that performs pretty much the same task, but does it with a nice GUI (Graphical User Interface). An incomplete version of the applet can be found in the folder, "GUI Stats Starter." This version displays the number of items entered by the user and their sum. The complete version that you will write will display several other statistics as well. The applet has a "Clear" button which should remove all the data from the dataset. In the original version, the Clear button is not functional. In your version, it should work properly. The final result should be essentially the same as the sample solution which you can see on a separate page. As you can see, you have to add the average, standard deviation, minimum, and maximum to the display.
The file that you have to modify is StatsApplet.java. You should read it, including the comments, to understand what is going on. (You can also read it here.) You will have to add a few new instance variables of type Label. And you will have to modify the methods init(), doEnterCommand, and doClearCommand(). You might want to take a look at the file StatCalc2.java. (You can read it here.) It contains a slightly modified version of the StatCalc class that you used in a previous lab. You will need to call several of the methods from this class.
In this exercise, you will work more directly with GUI components than you have in past labs. GUI components include things like buttons, text-input boxes, and pop-up menus. In Java, these are represented as objects belonging to the classes Button, TextField, and Choice.
Java also has other component classes. A Label is used for displaying text that can be read but not edited by the user. A Checkbox is a labeled box that the user can check and uncheck. A Panel is a component that can hold other components. (An applet is a type of panel, since the Applet class is a subclass of the Panel class.)
Components are added to an applet or panel using an "add()" method. The components that have been added to an applet or panel are laid out by a LayoutManager. A layout manager implements some policy about how components are to be sized and positioned. A "SetLayout()" method is used to specify the layout manager to be used.
When the user interacts with a component, an event occurs. Most of the standard components produce "action" events, which are handled in the applet's action() method. As a programmer, you write an action method to say what will happen when the user manipulates a button, checkbox, etc.
All this is discussed in Chapter 6 of the on-line text, but you don't need to know everything in that chapter to do the lab. Here are some specific facts that you do need:
- An object belonging to the class GridLayout is a layout manager that will arrange components into a regular grid of rows and columns. A GridLayout object can be created with a constructor "new GridLayout(R,C,VS,HS)", where R is the number of rows, C is the number of columns, VS is vertical space inserted between rows, and HS is the horizontal space inserted between columns.
- If bttn is of type Button, then bttn.disable() will deactivate the button so that the user can't click on it. The method bttn.enable() will make the button active again.
- If labl is of type Label and str is a string, then labl.setText(str) will change the text displayed by the label to str.
- If txt is of type TextField, then txt.getText() returns a String which is the text that is currently in the input box. The contents of the box can be set to a string str with txt.setText(str).
Exercises to Turn in
Exercise 1. Show what the following list would look like after each phase of insertion sort:
17 14 34 26 38 7 28 32
(On a list of length 8, there are 7 phases. After each phase, the sorted section of the list has increased in length by one.) This is for 3 points.
Exercise 2. Show what the following list would look like after each phase of merge sort:
17 94 64 56 38 92 74 32 23 12 11 63 74 35 43 21
There are four such phases for a list of length 16. Also, explain in words what has been accomplished by each phase. This is for 4 points.
Exercise 3. This exercise is based on the data you collected above about sorting algorithms. How many times faster than insertion sort is merge sort for lists of length 1000? For lists of length 5000? For lists of length 10000? For other lengths that you checked? How long do you think it would take insertion sort to sort 1,000,000 integers? Why? Try to explain why merge sort is so much faster than insertion and why its advantage grows as the number of items increases. (Hint: look at the number of phases in the two sorting methods for lists of size 16, 32, 64, ...). This is for 8 points.
Exercise 4. Turn in a printout of the modified StatsCalc.java file that you worked on above. Also post your applet on the Web. Tell me its URL (unless you are sure that I will be able to find it easily.) This is for 10 points.
Exercise 5. The xSortLab applet uses a lot of GUI components, managed by several different types of LayoutManagers. Try to figure out how the xSortLab applet's GUI is constructed. What components and layout managers do you think were used. It would be a good idea to illustrate your answer with some drawings. You probably will not be able to answer this question unless you have carefully read Section 6.1 of the on-line text. This is for 5 points.