Introduction to Computer Science

Summary of 11/27 Lecture

Sorting algorithms; nested loops.  (7.4)

Sorting Algorithms

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:

public boolean inorder(int [] a){
int i;
for (i = 1; i < a.length; i++) {
if (a[i-1] > a[i] ) return false;
}
return true;
}

This suggests a very simple way to place an array in order, by a "bubble sort":

public void bubbleSort(int [] a){
int i;
boolean inorder=false;
while (! inorder) {
inorder=true;
for (i = 1; i < a.length; i++) {
if (a[i-1] > a[i] ) {
int temp;

// exchange the out-of-order elements
temp = a[i-1];
a[i-1] = a[i];
a[i] = temp;
inorder = false;
}
}
}
}

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.

Practical Issues in Using 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)? ");
for (int k=0; k<n; k++)
{
}

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
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 [] number = new int [n];    //

for (int k=0; k<n; k++)
{
}

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
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? ");

//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++)
{
}

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
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

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).

Designing Solutions using Classes

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.

import iostuff.*;
{
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: ");
if (Keyboard.eof())
{
break;
}

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);
}
}
}

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.*;
{
static final int INPUT_MAX = 100;

public static void main (String[] arg)
{
}
}

import iostuff.*;
{
String [] names;
int []     exam1,
exam2;
int size = 0;    //Initialize counter

{
names = new String [number];
exam1 = new int [number];
exam2 = new int [number];
}

{
while (true)
{
System.out.print("Enter name and two exam grades: (CTL-Z to quit)");
if (Keyboard.eof())
{
break;
}

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;
}
}

import iostuff.*;
{
Student [] students;
int size = 0;

{
students = new Student [number];
}

{
String nextname;

while (true)
{
System.out.print("Enter name and two exam grades: ");

if (Keyboard.eof())
{
break;
}

students [size] = new Student();
students [size] . setName (nextname);
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());
}
}
}

import iostuff.*;
{
static final int INPUT_MAX = 100;

public static void main (String[] arg)
{
}
}

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).