char[][] a = {{'a','b'},{'x','y','d','q','r'},{'u','w','b','a'}};Note that a.length is 3, a[0].length is 2, a[1].length is 5, and a[2].length is 4.
char[][] a = new char[3][]; a[0] = new char[2]; a[1] = new char[5]; a[2] = new char[4];This technique is convenient when the length of each row is not known until runtime, as the lengths can be read in and the row arrays constructed accordingly.
File TwoD.java contains a shell for a program that reads in and prints out information about variable sized groups of people. This information will be stored in a two dimensional array, with each row representing one group. The program should ask the user for the number of groups and use this information to create the appropriate number of rows in the array. For each group it should then ask how many people are in the group and use this information to make that row of the array just the right length. It should then ask for the names for that group and store them in the array. After all the data has been entered, the names in each group should be listed. For example, a run of your program might look like this;
Enter number of groups: 3 Enter number of people in group 0: 2 Name 0: rachel Name 1: elly Enter number of people in group 1: 3 Name 0: spud Name 1: madison Name 2: floyd Enter number of people in group 2: 1 Name 0: beauty ** GROUP SUMMARY ** GROUP 0: rachel elly GROUP 1: spud madison floyd GROUP 2: beautyIn testing your program, try a group of size 0 (among others) to see what happens.
Print your program to turn in.
Now you will use these classes to examine the runtimes of the sorting and searching algorithms. You can do this using the java method long System.currentTimeMillis(), which returns the current system time in milliseconds. (Note that it returns a long, not an int.) You will have to import java.util.* to have access to this method. In IntegerListTest, just get the system time immediately before and immediately after you perform any of the searches or sorts. Then subtract the first from the second, and you have the time required for the operation in milliseconds. WARNING: Be sure you are not including any input or output in your timed operations; these are very expensive and will swamp your algorithm times! Also note that the first couple of times you run a method you might get longer runtimes as it loads the code for that method. Ignore these times and use the "steady-state" times you get on subsequent runs.
Add appropriate calls to System.currentTimeMillis() to your program and fill out the tables below. Note that you will use much larger arrays for the search algorithms than for the sort algorithms; do you see why? On a separate sheet, explain the times you see in terms of the known complexities of the algorithms. Remember that the most interesting thing is not the absolute time required by the algorithms, but how the time changes as the size of the input increases.
Array size | Selection sort (random array) | Selection sort (sorted array) | Insertion sort (random array) |
10,000 | |||
20,000 | |||
40,000 | |||
80,000 |
Array size | Sequential search (unsuccessful) | Binary search (unsuccessful) | Insertion sort (sorted array) |
100,000 | |||
200,000 | |||
400,000 | |||
800,000 | |||
1,600,000 |
Note: You can find out more about the I/O classes described here in the online Java documentation. Just look up the class you want to learn about in the lower lefthand box, which lists all Java classes. Or to limit the list to just the I/O classes, select the java.io package from the list in the upper lefthand box.
File FileIO.java contains a simple program that prompts for and reads in the name of a file and then copies the contents of that file, line by line, to the standard output. Save this file to your directory, open it in emacs, and study it to see how it works. Note that to read from the file, first a FileReader is created, then it is used to create a BufferedReader. It is often convenient to use a BufferedReader because it has a readLine() method, which returns an entire line of the input (not including the newline character). Also note that the main method throws an IOException; this is just to alert the Java system that this program could generate an I/O error.