CPSC 124: Lab 9
Sorting, Two-dimensional Arrays, and an Introduction to Files

THIS LAB CONTINUES THE STUDY OF ARRAYS. You will experiment with several different array-sorting algorithms and will implement an array-sorting routine. There is also an exercise that uses a two-dimensional array.

Exercise 1

The first exercise for this lab is an essay based on experimentation with several different sorting algorithms. The experiments should convince you that different algorithms can take remarkably different amounts of time to accomplish the same goal. For the experiments, you need to use the program xSortLab, which you can find on the file server. (This program was not written in Java.) Find the program and start it up.

This program can sort arrays using any of six sorting methods. The available methods are listed under the "Method" menu. Use this menu to select "Insertion Sort," which we have talked about in class. By clicking repeatedly on the "Next" button, you can step through the insertion sort algorithm and watch as sixteen bars are gradually arranged into increasing order. As you step through the algorithm, you can read a description of each step at the bottom of the window. If you click on the "Go" button, the algorithm will run by itself. (You can speed it up by selecting "Visual/Fast" from the "Speed" menu.)

Now, switch the Method to "Merge Sort". Click on the "New Sort" button to get a new array of bars. Step through the sort using the "Next" 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.

For the next part of the exercise, you should select the first option, "Timed/Uninterruptable", from the "Speed" menu. With this setting, you can ask the program to sort large arrays and tell you how long it takes. The timing information is displayed in another window, called the Log Window (which might be hidden behind the main xSortLab window).

Try sorting a single array of 1000 items using both Insertion Sort and Merge Sort. Write down the time it takes for each method. (Check the Log Window for this information; note that the time is measured in ticks where a tick is 1/60 second.) You could also try an array of 100 items, but it will take hardly any time at all to sort such an array, using either method.

Now, try sorting arrays of size 2000 with both methods, and record the timing information. Then do arrays of size 4000 and 8000. Finally, sort an array of size 100000 using Merge Sort. Don't try to use Insertion Sort on such a large array.

The exercise is to write a report on your experiments with watching merge sort in action and on your comparison of the running times of merge sort and insertion sort for large arrays. In particular:

Exercise 2

Exercise 2 is also about sorting. But in addition, it introduces you to the idea of files. A file represents information that has been saved onto the computer's hard disk or some other data storage medium. Programs can open existing files and read the data that they contain. They can also create new files and write data to files.

In Java, files are examples of streams. Streams are more general than files. There are two types of streams, input streams and output streams. A program can read data from an input stream and it can write data to an output stream. These two types of streams are represented in Java by the classes InputStream and OutputStream. These classes have subclasses FileInputStream and FileOutputStream to represent files that are being used for input or output.

The folder "Lab 9 File Starter" on the file server contains a sample program that uses files. The program reads all the words from an input file and writes them to an output file. The names of the input file and the output file are typed in by the user. The program does a fair amount of error-checking, using try...catch statements. You can read about try...catch statements, streams, and files in Chapter 8, but you don't need to know a great deal about them until Lab 10. For now, you can just read the comments in the program.

Copy the folder onto your computer. Open the folder, open the project file, and open the file "Application.java". You should read the comments on this file. Your assignment is to modify the program to store all the words it reads in an array, then sorts the array before printing all the words to the output file. You can assume that there are no more than 10000 words in the file, so you can use a "partially filled array"

          String[] words = new String[10000];
          int wordCt = 0;

As the program reads each word, instead of printing it to the output file, it should just add it to the array. After reading all the words from the input file, it should sort the array using either insertion sort or selection sort. Then it should use a for loop to print out all the words in the array to the output file.

You can find algorithms for insertion sort and selection sort in Section 7.3 of the notes. You will have to adapt the algorithm to the case of sorting an array of strings, since Strings cannot be compared using <. To find out if a string str1 is less than another string str2, use str1.compareTo(str2). This method returns an int value. If str1 is less than str2, the value is a negative integer. If str1 is greater than str2, the value is a positive integer. If they are equal, the value is zero.

Turn in a printout of the modified program.

Exercise 3

The final part of the lab is a short exercise using two-dimensional arrays. You will be making a few modifications to the applet in the folder "Lab 9 Cards Starter". Copy the folder onto your computer. Open the folder, open the project file, and open the file "CardsApplet1.java". You should read the comments on this file and try out the applet.

Right now, the applet let's you place cards on a playing area by clicking with the mouse. The applet has a two-dimensional array of cards that could be used to store information about which cards are on the playing area. But the array is not really being used in the applet as it stands.

Your assignment is to modify the applet so that each time a card is placed on the playing area, that card is also stored in the corresponding spot in the array, grid. You should also modify the applet's clear() routine so that it correctly begins a new game. The comments in the file give you more information.

Turn in a printout of the modified file.

[ Lab Index | Online Notes ]