In this next example we are going to solve a moderately complex problem involving a list of numbers. We will read this list of numbers from a text file and store the list in an array. We will then work with that array to solve the problem.
The problem is to find the integer in a list of integers that appears most often. An obvious strategy to solve this problem is to ask how many times each of the integers in the file appears in the file. As we work our way through the range of possible integers, we will record which integer has appeared most often.
The first step is to write the main method for our program. This main method will be fairly short, because at key points in the main method we are going to call other methods to help us with our work.
public static void main(String[] args) {
int numbers[] = readNumbers("numbers.txt");
// Find the smallest and largest numbers in the array
int smallest = findSmallest(numbers);
int largest = findLargest(numbers);
int greatestCount = 0;
int mostCommonNumber = 0;
for (int x = smallest; x <= largest; x++) {
// Count how many times x appears.
int count = countNumber(numbers,x);
// Check to see if this is the most common number.
if(count > greatestCount) {
greatestCount = count;
mostCommonNumber = x;
}
}
// Print the results
System.out.println(mostCommonNumber+" appears most often.");
System.out.println("It appears "+greatestCount+" times.");
}
To finish our program we need to write the code for four methods that we called in main. Here is a brief description of what each method should do.
readNumbers reads a list of ints from a file, puts them into an array, and returns that array to us.findSmallest finds and returns the smallest number in the array.findLargest finds and returns the largest number in the array.countNumber counts how many times a given number appears in the array.Here now is the code for each of these methods. Since each method has a clearly defined and relatively simple task to perform, writing the code for each individual method is not too hard.
public static int[] readNumbers(String fileName) {
Scanner input = null;
try {
input = new Scanner(new File(fileName));
} catch (Exception ex) {
ex.printStackTrace();
}
// We need to count the number of numbers first. We will read
// through the file once simply to count how many numbers are
// there...
int N = 0;
while (input.hasNextInt()) {
int unused = input.nextInt();
N++;
}
input.close();
// Once we know how many numbers are in the file we can create an
// array to hold them.
int[] A = new int[N];
// Now we have to read through the file again to put the numbers
// into the array.
try {
input = new Scanner(new File(fileName));
} catch (Exception ex) {
ex.printStackTrace();
}
int n = 0; // Where the next number will go.
while (input.hasNextInt()) {
A[n] = input.nextInt();
n++;
}
input.close();
return A;
}
public static int findSmallest(int A[]) {
int smallest = A[0];
for (int n = 1; n < A.length; n++) {
if (A[n] < smallest) {
smallest = A[n];
}
}
return smallest;
}
public static int findLargest(int A[]) {
int largest = A[0];
for (int n = 1; n < A.length; n++) {
if (A[n] > largest) {
largest = A[n];
}
}
return largest;
}
public static int countNumber(int A[], int x) {
int count = 0;
for (int n = 0; n < A.length; n++) {
if (A[n] == x) {
count++;
}
}
return count;
}
One great advantage of methods is that they are portable. Once we write the code for a method that solves a particular problem, we can reuse that same method in other projects where we have to solve the same problem. A good example of this is the readNumbers method. Many programs we will see in this course are going to require us to read a list of ints from a file and put those numbers in an array. To make this method even more flexible, I designed it to take the name of the file to be opened as its parameter. This makes it even easier to use the method in a different program.
A second project you will find at the top of these notes is a project that demonstrates the selection sort algorithm. The code in this project is taken pretty directly from the textbook. You can read more about select sort in section 7.11 in the textbook.
In many cases, being able to sort lists of data items opens up new approaches to solving problems. An example of this is the problem I solved at the start of these notes. An alternative strategy for solving this problem involves first sorting the list of numbers and then running search procedure that looks for runs of consecutive numbers.
If you sort a list of numbers that contains duplicates of some numbers, you will see those numbers forming runs of the same repeated number in the sorted list. Searching for these runs and determining which of the runs is the longest is a relatively straightforward problem.
Here is the main method for a program that uses this strategy to find the most common number in a file.
public static void main(String[] args) {
int numbers[] = readNumbers("numbers.txt");
// Sort the list
selectionSort(numbers);
// Find the most common number
int greatestCount = 1;
int mostCommonNumber = numbers[0];
for (int n = 1;n < numbers.length;n++) {
if(numbers[n] == numbers[n-greatestCount]) {
greatestCount++;
mostCommonNumber = numbers[n];
}
}
// Print the results
System.out.println("The number " + mostCommonNumber + " appears most often.");
System.out.println("It appears " + greatestCount + " times in the file.");
}
The loop here that searches for runs of the same number uses a simple strategy to detect a run. The if statement in the loop compares the next number in the list with a number several spaces back in the list. If these numbers are the same, we have discovered a run of a certain length. If that run length is greater than the greatest run length we have seen so far, we can record the details of that new, winning run of numbers.
Whenever we have more than one strategy for solving a problem, computer scientists compare the relative quality of these two solutions by comparing how much time the two strategies take to solve the problem. One way that computer scientists measure the run time efficiency of a program is to express the amount of time it takes as a function of the number of data items the program has to process.
If we have a list of N integers that we need to process, both solutions I showed today have a run time that is proportional to N2. In the first algorithm we have to count how many times each possible number appears. In a typical file, there will be roughly N items to count. A single pass through the array to count how many times an item appears takes time proportional to N, so the total work needed by the first algorithm is proportional to N2. In the second algorithm we have to sort the numbers and then do one pass through the list to determine the longest run. Sorting with selection sort takes time proportional to N2, while the run check takes time proportional to N. Once again, the second algorithm ends up taking time proportional to N2.
What makes the second algorithm superior in the end is the fact that we can replace selection sort with a more efficient sorting algorithm. In the lecture on Wednesday I will show a couple of sorting algorithms that can sort a list of integers in time proportional to N log N instead of N2. By using one of these more efficient sorting algorithms, we can reduce the time needed by the second method to N log N, which is a huge improvement over N2.