# Introduction to Computer Science

## Summary of 11/29 Lecture

Instantiating objects.  More on nested loops.  (9.1)

### More on Sorting

We will look more at sorting and consider nested loops and instances of objects.

Two commonly used sorts are QuickSort (due to C.A.R. Hoare) and ShellSort (due to D. L. Shell). Quicksort work by partitioning the original array into two subsets based on elements being more of less than a "pivot point" and then recursively sorting the subsets. The ShellSort is based on dividing the original array into subsets based on increasingly fine combs. We will start with a variant of the variant of the ShellSort based on simple bubble sorts.

public static void sortComb(int [] a, int g){

// This method sorts the subset of the array a
// consisting of elements separated by the gap g

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

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

}
}
}
}

public static void ShellSort(int [] a ) {

// This method uses sortComb to progressively bring
// array a into order by sortsusing finer and finer combs
// ending with an ordinary bubble sort.

int gap = a.length/2;
while ( gap > 0 ) { sortComb(a, gap);
gap /= 2;
}
}

Now let us look at a QuickSort.   In order to allow the sort to work recursively on portions of the array, we need to add pointers into the array

public static int QuickSortPart(int [] a, int lo, int hi ) {

// This method reorganizes the array arround a pivot
// point so that all the elements to the left are no larger
// than the array element at the pivot and all the elements
// at to the right are no smaller than the array
// element at the pivot.

int temp;

if (hi > lo) {

int below=lo+1, above=hi;

while (below < above) {

while (below < hi+1 && a[below] <= a[lo]) below++;
while (above > lo && a[above] >= a[lo]) above--;
if (below < above) {
temp = a[below];
a[below] = a[above];
a[above] = temp;
}
}
if (above > lo) {
temp = a[lo];
a[lo] = a[above];
a[above] = temp;
}
return above;
}
return lo;
}

public static void QuickSortSeg(int [] a, int lo, int hi) {

int pivot;

if (hi > lo) {

pivot = QuickSortPart(a, lo, hi);
// Note:  everything to the left of the pivot
// is no larger than a[pivot], and everything
// to the right of the pivot is no smaller
// then a[pivot] so there is no further
// merge to do.
QuickSortSeg(a, lo, pivot-1);
QuickSortSeg(a,pivot+1,hi);
}
}

public static void QuickSort(int [] a) {

QuickSortSeg(a, 0, a.length-1);
}

In the book you will find material on other sorts.  Of particular interest are sorts which merge new data into previously sorted segments of data.  A point to bear in mind in doing this is that it is much more efficient to progressively divide the sorted array into halves than to work up sequentially from the bottom.

### Reference vs Value Parameters

Recall that Java provides two distinct data types, primitive (int, double, char, boolean) and objects (String, TextField, Button, etc.).  That distinction is relevant to the task of passing parameters to methods (functions).  Consider the following example:

//File:    TestParameters.java
public class TestParameters
{
public static void changeParams (int [] a, int b)
{
a[1]     = 100;
b    = 50;
}

public static void main (String [] args)
{
int [] list = {12, 15, 23};
int x = 3;

System.out.println ("BEFORE CHANGE");
for (int k=0; k<list.length; k++)
{
System.out.println ("list[" + k + "] = "
+ list[k]);
}
System.out.println ("x = " + x);
System.out.println();

changeParams (list, x);

System.out.println ("AFTER CHANGE");
for (int k=0; k<list.length; k++)
{
System.out.println ("list[" + k + "] = "
+ list[k]);
}
System.out.println ("x = " + x);
}
}

>java TestParameters
BEFORE CHANGE
list[0] = 12
list[1] = 15
list[2] = 23
x = 3

AFTER CHANGE
list[0] = 12
list[1] = 100
list[2] = 23
x = 3

Note that the value of list[1] has been changed by the changeParams() method whereas the value of x has NOT been changed.  Since arrays are objects, the parameter "a" is a reference parameter.  That is, it refers to the array "list" defined in the main() method.  In effect, whatever happens to the array "a" in the changeParams() method happens by reference to the array "list" in the calling method.  By contrast, the parameter "b" is a primitive data type (int).  It is therefore given its own memory location, distinct from that of the corresponding actual parameter, "x".  So if the value of b is changed in the changeParams() method, the value of x in main() is unaffected.  This type of parameter is called a value parameter.  To summarize, parameters or arguments which are objects are reference parameters and therefore will update the corresponding actual parameter, while arguments of primitive data types are value parameters receiving their own distinct memory locations, and although they are initialized with the value of the actual parameter, they cannot themselves change the values of the actual parameter.

### The Student class lab revisited

Recall the lab exercise from our last meeting.  Let's work our way through the requirements.

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.

private int exam1, exam2;
becomes
private int [] exam = new int [2];
(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).
public int getExam1 ()
{
return exam1;
}

public int getExam2 ()
{
return exam2;

becomes
public int getExam (int which)
{
return exam[which-1];
}
{
System.out.print(
"How many grades for this 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.

Here, we expanded upon the requirements to allow the possibility that there are any number of scores.  In addition, we employed a divide and conquer approach to dropping the lowest grade.  The results of our labors are to found in the following updated version of the Student class.

//File:    Student.java
import iostuff.*;
class Student
{
//Data fields
private String name;
private int [] exam;
private int number_of_scores;

//Constructor
public Student ()
{
exam = new int [15];
}

public Student (String person, int n)
{
name = person;
exam=new int [n];
number_of_scores=n;
}

//Accessor methods
public String getName ()
{
return name;
}

public int getExam (int which)
{
return exam [which-1];
}

public int average ()
{
int sum=0;
for (int k=0; k<number_of_scores; k++)
{
sum=sum+exam[k];
}
return sum/number_of_scores;
}

//Mutator methods
public void setName (String s)
{
name = s;
}

public void setExam (int which, int s)
{
exam[which-1] = s;
}

public void setNumberOfScores(int n)
{
number_of_scores=n;
}

//The following two methods should
//method required in

//The following method returns the
//index of the smallest
//exam score.

public int smallestIndex()
{
int smallest=0;
for (int k=1; k<number_of_scores; k++)
{
if (exam[k] < exam[smallest])
smallest=k;
}
return smallest;
}

//The following method
//accomplishes the exchange of
//exam[i] and exam[j]. For example,
//this would allow you to place
//the lowest exam score "out of the way", //at the end of the
//list of exam scores.

public void swap (int i, int j)
{
int temp=exam[i];
exam[i] = exam[j];
exam[j] = temp;
}
//Required for Homework #5
//precondition: exam[0], exam[1],
// exam[2], ..., exam[numberOfScores-1]

{
}
//postcondition: exam[numberOfScores-1]
// contains smallest score in list
// numberOfScores = numberOfScores-1

//The following is just a "dummy" version of the
//standard deviation algorithm. You'll rewrite it to
//do the job required.

public int standardDeviation()
{
return 1;
}

//File:    TestStudent.java
import iostuff.*;
public class TestStudent
{
public static void main (String [] args)
{
Student s = new Student();

s.setName("Bill");
s.setNumberOfScores(2);
s.setExam(1, 98);
s.setExam(2, 50);
System.out.println (
"The average Score for " + s.getName()
+ " is: " + s.average());

Student s2 = new Student("Joe", 3);

s2.setExam(1, 94);
s2.setExam(2, 83);
s2.setExam(3,100);
System.out.println (
"The average Score for " + s2.getName()
+ " is: " + s2.average());
}
}

>java TestStudent
The average Score for Bill is: 74
The average Score for Joe is: 92

Adapted from Bill Steinmetz's course summary by H. J. Bernstein, 29 Nov 01