CPSC 124, Winter 1998
Sample Answers to Lab 9
This page contains sample answers to the exercises from Lab #9 in CPSC 124: Introductory Programming, Winter 1998. See the information page for that course for more information.
Exercise 1: The list can be thought of as divided into two parts, the sorted part and the unsorted part. In each phase, the first number in the unsorted part is inserted into the sorted part of the list. Here is how it goes (with the sorted part of the list shown in red).
Start: 17 14 34 26 38 7 28 32 Phase 1: 14 17 34 26 38 7 28 32 Phase 2: 14 17 34 26 38 7 28 32 Phase 3: 14 17 26 34 38 7 28 32 Phase 4: 14 17 26 34 38 7 28 32 Phase 5: 7 14 17 26 34 38 28 32 Phase 6: 7 14 17 26 28 34 38 32 Phase 7: 7 14 17 26 28 32 34 38
Exercise 2: Initially, the list is completed unsorted. However, we can think of it as being made up of sorted lists of length one. In the first phase, these lists are merged by pairs into sorted lists of length two. In the second phase, the lists of length two are merged into sorted lists of length four. And so on. In each phase, the length of the sorted lists doubles. In this example, it only takes four phases until the entire list is sorted. Here is how it looks. The sorted lists are underlined.
Start: 17 94 64 56 38 92 74 32 23 12 11 63 74 35 43 21 Phase 1: 17 94 56 64 38 92 32 74 12 23 11 63 35 74 21 43 Phase 2: 17 56 64 94 32 38 74 92 11 12 23 63 21 35 43 74 Phase 3: 17 32 38 56 64 74 92 94 11 12 21 23 35 43 63 74 Phase 4: 11 12 17 21 23 32 35 38 43 56 63 64 74 74 92 94
Exercise 3: Time measurements for merge sort and insertion sort will vary depending on the computer on which you run the xSortLab applet. (It also depends on which implementation of Java you are using). Here are some times (measured in seconds) for insertion sort and merge sort running under Netscape 4.04 on a 266-Megahertz Pentium II chip:
Number of Sorting time Sorting time Merge sort is this items in array for Insertion Sort for Merge sort many times faster ---------------- -------------------- ---------------- ---------------------- 100 .00045 .00021 2.1 1,000 .05 .0029 17.2 5,000 1.3 .019 68.4 10,000 4.3 .042 102 100,000 434 .609 712 1,000,000 (not done) 7.3Note that when the number of items is increases by a factor of 10, the sort time for insertion sort increases by about a factor of 100. So, my estimated time for merge sort to sort 1,000,000 would be about 43000 seconds. This is about 7200 minutes, or 120 hours.
Merge sort is so much faster than insertion sort because it uses far fewer "phases" (while the phases of merge sort and insertion sort take comparable amounts of time). To sort n items, insertion sort uses n-1 phases. On the other hand, the number of phases used by merge sort is the same as the number of times that n can be divided by 2 before a result less than one is obtained. In mathematics, this number is, approximately, the "logarithm of n in the base 2." For 16 items, insertion sort uses 15 phases while merge sort uses 4. More generally to sort 2k items, insertion sort uses 2k-1 phases while merge sort uses only k phases. This is a huge difference, and the difference grows as k gets bigger. For example, merge sort only needs 20 phases to sort 1,000,000 items, since 1,000,000 is about 220, while insertion sort uses 999,999 phases.
(We can get a little more exact by looking at how long individual phases take. Assume that the list is initially in a random order. For insertion sort, on the average, the size of the sorted list is n/2, and the sort procedure has to look at half of these n/2 elements, on average. Therefore, on average, insertion sort does about n/4 "operations" during each phase. Because there are about n phases, the total number of operations used by insertion sort is, on the average, about n2/4. The time it takes for insertion sort to sort n items is, therefore, proportional to n2. Merge sort, on the other hand does n operations for each phase (or 2*n, depending on what you count). It uses log(n) phases (where log(n) is the base-2 logarithm of n). So the total number of operations for merge sort is about n*log(n), and the time it takes for merge sort to sort n items is proportional to n*log(n). Note that as n goes to infinity, the ratio between n2 and n*log(n) also goes to infinity. So the advantage of merge sort over insertion sort increases without limit as n increases.)
Exercise 4: Here is a copy of the modifies version of StatsApplet.java file. Parts that have been added or modified are shown in blue.
/* This applet is simple statistics calculator. It will compute and display various statistics about a set of numbers entered by the user. */ import java.awt.*; import java.applet.Applet; public class StatsApplet extends Applet { TextField dataField; // A text-input box where the user will enter the numbers Button enterButton; // The user can click on this button to enter a numbers // into the data set. (Numbers can also be entered // just by pressing return.) Button clearButton; // The user can clear the dataset by clicking on this button. Label countText; // Uneditable text that shows the number of numbers in the dataset. Label sumText; // Uneditable text that shows the sum of the numbers. Label maxText; // Uneditable text that shows the maximum of the numbers. Label minText; // Uneditable text that shows the minimum of the numbers. Label meanText; // Uneditable text that shows the average of the numbers. Label sdText; // Uneditable text that shows the standard deviation of the numbers. StatCalc2 stats; // A statistics object object to keep track of the data. public void init() { // The init method is called by the system when the applet object // is first created. It is used here to create and lay out // the components that make up the applet. setBackground(Color.lightGray); setLayout( new GridLayout(7,2,3,3) ); // changed from 3 rows to 7 // Applet will show a grid of components in seven rows and two // columns. (The third and fourth parameters specify space // between components in the grid.) stats = new StatCalc2(); // create the StatCalc2 object dataField = new TextField(); // create componets enterButton = new Button("Enter"); clearButton = new Button("Clear"); clearButton.disable(); // The clear button is initially // disabled because there is no // data to clear. countText = new Label("0"); sumText = new Label("0"); meanText = new Label("0"); sdText = new Label("undefined"); maxText = new Label("undefined"); minText = new Label("undefined"); Panel buttonPanel = new Panel(); // The two buttons will be placed // in a sub-panel that uses a grid // layout with a single row and two // columns. The sub-panel will then // be added as a single component in // the applet layout. buttonPanel.setLayout( new GridLayout(1,2,3,3) ); buttonPanel.add(enterButton); buttonPanel.add(clearButton); add(dataField); // Add components to the applet. add(buttonPanel); // The components are laid out add( new Label("Items entered:") ); // by the GridLayout layout manager. add(countText); // It fills in the grid row by row. add( new Label("Sum:") ); // There should be as many components add(sumText); // as there are spaces in the grid. add( new Label("Average:") ); add(meanText); add( new Label("Standard Deviation:") ); add(sdText); add( new Label("Maximum:") ); add(maxText); add( new Label("Minimum:") ); add(minText); } // end of init() method. public Insets insets() { // This method is called by the system to find out how much space // there should be between the edges of the applets and the components // contained in the applet. return new Insets(3,3,3,3); } public void start() { // This is called by the system just before the applet starts running dataField.requestFocus(); } void doEnterCommand() { // This method is called by the action() method, defined below, // when the user enters a number into the data set (by clicking // on the Enter button or by pressing return while typing in // the dataField text-input box. String dataText = dataField.getText(); // Get the text from the input box. double n; // This section of the method converts try { // the string from the input box Double d = new Double(dataText); // into a double number. It's kind n = d.doubleValue(); // of tricky. } catch (NumberFormatException e) { // If an error is found in the input, dataField.setText("Illegal Entry!"); // A message is put in the input box. dataField.selectAll(); dataField.requestFocus(); return; } stats.enter(n); // Add the user's number to the dataset. int count = stats.getCount(); // Show the stats. countText.setText( String.valueOf(count) ); double sum = stats.getSum(); sumText.setText( String.valueOf(sum) ); double mean = stats.getMean(); meanText.setText( String.valueOf(mean) ); double sd = stats.getStandardDeviation(); sdText.setText( String.valueOf(sd) ); double min = stats.getMinimum(); minText.setText( String.valueOf(min) ); double max = stats.getMaximum(); maxText.setText( String.valueOf(max) ); dataField.selectAll(); // Hilites the contents of the text box. dataField.requestFocus(); // Asks for the text box to get the input focus. if (count == 1) // If the first item has just been entered, clearButton.enable(); // then the clear button can be enabled. } // end doEnterCommand() void doClearCommand() { // This is called by the action() method when the user clicks on the Clear button. stats.clear(); // clear the dataset in the stats object clearButton.disable(); // clear button can be disabled since there is nothing to clear countText.setText("0"); // clear the statistics displays. sumText.setText("0"); meanText.setText("0"); sdText.setText("undefined"); minText.setText("undefined"); maxText.setText("undefined"); dataField.selectAll(); dataField.requestFocus(); } public boolean action(Event evt, Object arg) { // This is called by the system when the user performs some action on // one of the components in the applet. if (evt.target == enterButton) { // use clicked Enter button doEnterCommand(); return true; } else if (evt.target == clearButton) { // user clicked Clear button doClearCommand(); return true; } else if (evt.target == dataField) { // user pressed return while typing doEnterCommand(); // in the data-input box return true; } else return super.action(evt,arg); } // end action() } // end of class StatsApplet
Exercise 5: The xSortLab applet uses a lot of different components an a lot of Panels and LayoutManagers. The main structure of the applet uses a BorderLayout. The "North" component of this layout is a Choice component which displays the choices "Visual Sort," "Timed Sort," and "Log." The "Center" component is a Panel that uses a CardLayout. The card layout has three cards: one for Visual Sort, one for Timed Sort, and one for the Log.
Each of the three cards managed by the CardLayout is itself a Panel, and each of these three Panels used a BorderLayout for its main structure. The Log panel has a TextArea in the Center of the layout, with a Panel holding two Buttons to the South. The Timed Sort Panel has a Canvas in the Center with Panels to North and South. The North panel holds two Labels and two TextFields. The South Panel holds a Choice component and a Button. (Of course, the Canvas in the Center is actually a member of a subclass of Canvas.)
The Visual Sort page is the most complicated. In the Center is a canvas (belonging to a subclass of Canvas) on which the action takes place. To the right are a Choice, a Checkbox, three Buttons and four Labels. At the south are two small Canvases that are used as message display areas. (You would probably mistake them for Labels.) The two little canvases are in a GridLayout with two rows and one column. (The stuff at the right might look like its in a GridLayout, but actually the layout of this part is done by hand, since that was the only way to get the exact proportions that I wanted. Note that it can't be a single Panel with a GridLayout because the background is gray in the top half and white in the bottom half.)
David Eck, 12 March 1998