Sorting algorithms; nested loops. (7.4)
The basics of sorting and searching are covered in section 7.4 of the text and efficient algorithms are considered in chapter 8.
Arrays are like file cabinets, and allow us to store information in an organized manner. As with a file cabinet, it is easier to find information in an array if it has been placed in order, if it has been sorted.
We can tell if an array if out of order by comparing each element of the array to the next one, as in the following method:
This suggests a very simple way to place an array in order, by a "bubble sort":
We keep running through the array again and again as long as any elements are out of order. We always make a full pass through the array when it is in order. This is a very inefficient, but reliable sort. It is more efficient if we organize our sort to move out-of-order elements closer to their final destination in fewer steps. Before we turn to more efficient sort methods, let us work on some practical issues with arrays.
The following three driver programs test drive our NumberList class and illustrate the mechanics of creating and using arrays.
//File: TestNumberList.java
import iostuff.*;
public class TestNumberList
{
public static void main (String [] args)
{
int [] number = {10, 20, 30};
//Reserves exactly 3 memory locations
//AND assigns: number[0]=10, number[1]=20, number[2]=30
System.out.println ("The list of numbers
is: " );
NumberList.display(number);
System.out.println ("The smallest number
in the list is: "
+ NumberList.smallest (number));
System.out.println ("The average of the
list of numbers is: "
+ NumberList.average (number));
}
}
>java TestNumberList
The list of numbers is:
10
20
30
The smallest number in the list is: 10
The average of the list of numbers is: 20
Of course, in this version, the number of items in the list as well as the values are "hardwired" in the program. That is, there is no provision for user input. The following driver program creates an array capable of holding 10 integers. Note that it is not required that all of the 10 memory locations be occupied. User input is required to assign values to the array elements.
//File: TestNumberList1.java
import iostuff.*;
public class TestNumberList1
{
public static void main (String [] args)
{
int [] number = new
int [10]; //Makes room for 10 int's.
//labelled number[0], number[1], ... number[9]
//Note: If the number of items
in your list, n, is smaller than 10
//
then the remaining unoccupied locations represent "wasted"
//
space.
System.out.print ("How many numbers in
your list (up to 10)? ");
int n=Keyboard.readInt();
for (int k=0;
k<n; k++)
{
System.out.print
("Number please: ");
number[k] =
Keyboard.readInt();
}
System.out.println ("The list of numbers
is: " );
NumberList.display(number);
System.out.println ("The smallest number
in the list is: "
+ NumberList.smallest (number));
System.out.println ("The average of the
list of numbers is: "
+ NumberList.average (number));
}
}
>java TestNumberList1
How many numbers in your list (up to 10)? 3
Number please: 10
Number please: 20
Number please: 30
The list of numbers is:
10
20
30
0
0
0
0
0
0
0
The smallest number in the list is: 0
The average of the list of numbers is: 6
The 7 trailing zeroes occur because the length of the array, "number", is 10,
whereas only 3 numbers were input into the list. Also, notice that the average (6)
is the average of all 10 numbers in the list, INCLUDING THE ZEROES!
The last driver program illustrates the ability of Java to accommodate the dynamic (run-time rather than compile-time) allocation of arrays. In this example, the computer establishes exactly as many memory locations as are needed in the application.
//File: TestNumberList2.java
import iostuff.*;
public class TestNumberList2
{
public static void main (String [] args)
{
System.out.print ("How many numbers in
your list? ");
int n=Keyboard.readInt();
int [] number = new
int [n]; //
for (int k=0;
k<n; k++)
{
System.out.print
("Number please: ");
number[k] =
Keyboard.readInt();
}
System.out.println ("The list of numbers
is: " );
NumberList.display(number);
System.out.println ("The smallest number
in the list is: "
+ NumberList.smallest (number));
System.out.println ("The average of the
list of numbers is: "
+ NumberList.average (number));
}
}
>java TestNumberList2
How many numbers in your list? 3
Number please: 10
Number please: 20
Number please: 30
The list of numbers is:
10
20
30
The smallest number in the list is: 10
The average of the list of numbers is: 20
We have achieved the flexibility of user input for assigning values to the array as well
as conserving memory by allocating only as many memory locations as required to
accommodate our list. Since the length of the array is identical to the number of
values input by the user, the average correctly calculates (10+20+30)/3 = 20.
Finally, we discussed the merits of separating the input of values from the calculation of averages. The following method isolates the input task from the others represented in the NumberList class. Note that the return value for this method is itself an array of int's.
public static int [] inputList ()
{
System.out.print ("How many items in your
list? ");
int n=Keyboard.readInt();
//allocate n memory locations for array x
int [] x = new
int [n];
//fill the array x with values from the user
for (int k=0;
k<n; k++)
{
System.out.print
("Next number please: ");
x [k] =
Keyboard.readInt();
}
return x;
//return the filled array x
}
We'll add this to our NumberList class. The following program test drives all the methods in the NumberList class.
//File: NumberListDriver.java
import iostuff.*;
public class NumberListDriver
{
public static void main (String [] args)
{
int [] number =
NumberList.inputList();
System.out.println ("The list of numbers
is: " );
NumberList.display(number);
System.out.println ("The smallest number
in the list is: "
+ NumberList.smallest (number));
int avg = NumberList.average
(number);
System.out.println ("The average of the
list of numbers is: "
+ avg);
System.out.println ("The standard
deviation of the list is: "
+ NumberList.sd (number, avg));
}
}
>java NumberListDriver
How many items in your list? 3
Next number please: 10
Next number please: 20
Next number please: 30
The list of numbers is:
10
20
30
The smallest number in the list is: 10
The average of the list of numbers is: 20
The standard deviation of the list is: 8
To download and examine the latest version of our NumberList class, just click on NumberList.java.
Lab Exercise. Write a method that returns the location at which a number first occurs in a list of integers. Return -1 if it does not occur at all. The signature of the method (or function) looks as follows:
public static int find (int [] a, int p)
Test your function by looking for the value 24 in the list {12, 5, 39, 24, 59, 29, 18, 24}. It should return the value 3. Test it also on a list that does not contain the value 24.
After you've tried your hand, you might want to compare notes with me (FindNumber.java).
We began by considering the following problem:
Exercise. Write a program that simulates a gradebook with a list of students and two exam scores. The program asks the user for a name and two grades, exiting when encountering an end of file (CTL-z). The program then calculates the average grade for each person and outputs the names and averages.
//File: Grades.java
import iostuff.*;
class Grades
{
static final int INPUT_MAX = 100;
public static void main (String [] args)
{
String [] name = new
String [INPUT_MAX];
int [] exam1
= new int [INPUT_MAX];
int [] exam2
= new int [INPUT_MAX];
int size=0;
while (true)
{
System.out.print("Enter name and two exam grades: ");
name [size] =
Keyboard.readString();
if
(Keyboard.eof())
{
break;
}
exam1 [size] =
Keyboard.readInt();
exam2 [size] =
Keyboard.readInt();
size++;
}
System.out.println("\n\n\tName\tAverage");
for (int i=0;
i<size; i++)
{
System.out.println("\t" + name [i] +
"\t" + (exam1 [i] + exam2 [i])/2);
}
}
}
>java Grades
Enter name and two exam grades: Bill
92
100
Enter name and two exam grades: Joe
45
78
Enter name and two exam grades: CTL-Z
Name Average
Bill 96
Joe 61
Exercise. Rewrite the previous program by creating a Gradebook class.
import iostuff.*;
class ReadAndAvg
{
static final int INPUT_MAX = 100;
public static void main (String[]
arg)
{
GradeBook0 grades = new
GradeBook0(INPUT_MAX);
grades.readAndAverage();
}
}
//File: GradeBook0.java
import iostuff.*;
class GradeBook0
{
String [] names;
int [] exam1,
exam2;
int size = 0; //Initialize counter
public GradeBook0(int number)
{
names = new String [number];
exam1 = new int [number];
exam2 = new int [number];
}
public void readAndAverage()
{
// Read names and exam grades; size counts
inputs
while (true)
{
System.out.print("Enter name and two exam grades: (CTL-Z to quit)");
names [size] =
Keyboard.readString();
if
(Keyboard.eof())
{
break;
}
exam1 [size] =
Keyboard.readInt();
exam2 [size] =
Keyboard.readInt();
size++;
}
//System.out.println("\n\n");
System.out.println("\n\n\tName\tAverage");
for (int i=0;
i<size; i++)
{
System.out.println("\t" + names [i] +
"\t" + (exam1 [i] + exam2 [i])/2);
}
}
}
Note that in this implementation, the gradebook is characterized by 3 arrays, names, exam1, and exam2. Why not create a Student class with three attributes, a name and two scores; then represent the gradebook as an array of Student type?
//File: Student.java
import iostuff.*;
class Student
{
//Data fields
private String name;
private int exam1, exam2;
//Constructor
public Student ()
{
}
//Accessor methods
public String getName ()
{
return name;
}
public int getExam1 ()
{
return exam1;
}
public int getExam2 ()
{
return exam2;
}
public int getAvg ()
{
return (exam1+exam2)/2;
}
//Mutator methods
public void setName (String s)
{
name = s;
}
public void setExam1 (int s)
{
exam1 = s;
}
public void setExam2 (int s)
{
exam2 = s;
}
}
//File: GradeBook.java
import iostuff.*;
class GradeBook
{
Student [] students;
int size = 0;
public GradeBook(int number)
{
students = new Student
[number];
}
public void readAndAverage()
{
// Read names and exam grades; size counts
inputs
String nextname;
while (true)
{
System.out.print("Enter name and two exam grades: ");
nextname =
Keyboard.readString();
if
(Keyboard.eof())
{
break;
}
students [size] = new
Student();
students [size] .
setName (nextname);
students [size] .
setExam1 (Keyboard.readInt());
students [size] .
setExam2 (Keyboard.readInt());
size++;
}
System.out.println();
System.out.println();
System.out.println("\tName\tAverage");
for (int i=0;
i<size; i++)
{
System.out.println("\t" + students [i] . getName() +
"\t" + students [i] . getAvg());
}
}
}
//File: ReadAndAvg.java
import iostuff.*;
class ReadAndAvg
{
static final int INPUT_MAX = 100;
public static void main (String[] arg)
{
GradeBook grades = new
GradeBook(INPUT_MAX);
grades . readAndAverage();
}
}
Perhaps we could add a method to calculate the class averages on each of the exams. We did just that for the Exam1 scores by adding the following method to the GradeBook class:
public int classAvg1()
{
int sum=0;
for (int k=0;
k<size; k++)
{
sum+=students[k].getExam1();
}
return sum/size;
}
Clearly you could create a similar method, classAvg2(), to calculate the average of the Exam2 scores. This gets to be cumbersome as we add more exams. Perhaps we could add a data field to the GradeBook class, say int [] classAverage, that would maintain the averages for any number of exams? This leads naturally to the following Lab Exercise.
Lab Exercise. (page 216/#2) An advantage of the last version of GradeBook (the one that uses Student.java) is that computations relating to student grades can be encapsulated in the Student class. For example, we can change the number of grades and the way in which the average is calculated. Make the following changes in that version of GradeBook, in sequence:
(a) A better way to represent a student with several grades is to use a string for the student's name, as we already have, and an array for the grades. Make this change. For now, each student object contains an array of size two.
(b) In preparation for adding more grades per student, replace the methods getExam1() and getExam2() by a single method, getExam (int which). getExam (i) will return the grade on exam i (i being, of course, either 1 or 2).
(c) Add a method
public int numberOfGrades()
to Student. The input loop in readAndAverage() should call this method to determine how many grades to read for each student.(d) Add two more exam grades for each student. Furthermore, drop each student's lowest grade. That is, let getAvg() return the average of the three highest grades. If you have done the previous parts of this exercise correctly, this last change should be very simple.
Adapted from Bill Steinmetz's course summary by H. J. Bernstein, 26 Nov 01