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.

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.
 
 

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

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;

private int [] exam = new int [2];

    public int getExam1 ()
    {
           return exam1;
    }

    public int getExam2 ()
    {
           return exam2;

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

public int numberOfGrades()
{

System.out.print(
"How many grades for this student? ");
return Keyboard.readInt();

}

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
//make the dropLowestGrade()
//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]

public void dropLowestGrade()
    {
    }
//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());
    }
}

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