This chapter is from the book
This chapter is from the book
This chapter is from the book
Sorting Objects
For simplicity we've applied the sorting algorithms we've looked at thus far to a primitive data type: long. However, sorting routines will more likely be applied to objects than primitive types. Accordingly, we show a Java program in Listing 3.4, objectSort.java, that sorts an array of Person objects (last seen in the classDataArray.java program in Chapter 2).
Java Code for Sorting Objects
The algorithm used in our Java program is the insertion sort from the preceding section. The Person objects are sorted on lastName; this is the key field. The objectSort.java program is shown in Listing 3.4.
LISTING 3.4 The objectSort.java Program
// objectSort.java
// demonstrates sorting objects (uses insertion sort)
// to run this program: C>java ObjectSortApp
////////////////////////////////////////////////////////////////
class Person
{
private String lastName;
private String firstName;
private int age;
//-----------------------------------------------------------
public Person(String last, String first, int a)
{ // constructor
lastName = last;
firstName = first;
age = a;
}
//-----------------------------------------------------------
public void displayPerson()
{
System.out.print(" Last name: " + lastName);
System.out.print(", First name: " + firstName);
System.out.println(", Age: " + age);
}
//-----------------------------------------------------------
public String getLast() // get last name
{ return lastName; }
} // end class Person
////////////////////////////////////////////////////////////////
class ArrayInOb
{
private Person[] a; // ref to array a
private int nElems; // number of data items
//--------------------------------------------------------------
public ArrayInOb(int max) // constructor
{
a = new Person[max]; // create the array
nElems = 0; // no items yet
}
//--------------------------------------------------------------
// put person into array
public void insert(String last, String first, int age)
{
a[nElems] = new Person(last, first, age);
nElems++; // increment size
}
//--------------------------------------------------------------
public void display() // displays array contents
{
for(int j=0; j<nElems; j++) // for each element,
a[j].displayPerson(); // display it
System.out.println("");
}
//--------------------------------------------------------------
public void insertionSort()
{
int in, out;
for(out=1; out<nElems; out++) // out is dividing line
{
Person temp = a[out]; // remove marked person
in = out; // start shifting at out
while(in>0 && // until smaller one found,
a[in-1].getLast().compareTo(temp.getLast())>0)
{
a[in] = a[in-1]; // shift item to the right
--in; // go left one position
}
a[in] = temp; // insert marked item
} // end for
} // end insertionSort()
//--------------------------------------------------------------
} // end class ArrayInOb
////////////////////////////////////////////////////////////////
class ObjectSortApp
{
public static void main(String[] args)
{
int maxSize = 100; // array size
ArrayInOb arr; // reference to array
arr = new ArrayInOb(maxSize); // create the array
arr.insert("Evans", "Patty", 24);
arr.insert("Smith", "Doc", 59);
arr.insert("Smith", "Lorraine", 37);
arr.insert("Smith", "Paul", 37);
arr.insert("Yee", "Tom", 43);
arr.insert("Hashimoto", "Sato", 21);
arr.insert("Stimson", "Henry", 29);
arr.insert("Velasquez", "Jose", 72);
arr.insert("Vang", "Minh", 22);
arr.insert("Creswell", "Lucinda", 18);
System.out.println("Before sorting:");
arr.display(); // display items
arr.insertionSort(); // insertion-sort them
System.out.println("After sorting:");
arr.display(); // display them again
} // end main()
} // end class ObjectSortApp
////////////////////////////////////////////////////////////////
Here's the output of this program:
Before sorting: Last name: Evans, First name: Patty, Age: 24 Last name: Smith, First name: Doc, Age: 59 Last name: Smith, First name: Lorraine, Age: 37 Last name: Smith, First name: Paul, Age: 37 Last name: Yee, First name: Tom, Age: 43 Last name: Hashimoto, First name: Sato, Age: 21 Last name: Stimson, First name: Henry, Age: 29 Last name: Velasquez, First name: Jose, Age: 72 Last name: Vang, First name: Minh, Age: 22 Last name: Creswell, First name: Lucinda, Age: 18 After sorting: Last name: Creswell, First name: Lucinda, Age: 18 Last name: Evans, First name: Patty, Age: 24 Last name: Hashimoto, First name: Sato, Age: 21 Last name: Smith, First name: Doc, Age: 59 Last name: Smith, First name: Lorraine, Age: 37 Last name: Smith, First name: Paul, Age: 37 Last name: Stimson, First name: Henry, Age: 29 Last name: Vang, First name: Minh, Age: 22 Last name: Velasquez, First name: Jose, Age: 72 Last name: Yee, First name: Tom, Age: 43
Lexicographical Comparisons
The insertSort() method in objectSort.java is similar to that in insertSort.java, but it has been adapted to compare the lastName key values of records rather than the value of a primitive type.
We use the compareTo() method of the String class to perform the comparisons in the insertSort() method. Here's the expression that uses it:
a[in-1].getLast().compareTo(temp.getLast()) > 0
The compareTo() method returns different integer values depending on the lexicographical (that is, alphabetical) ordering of the String for which it's invoked and the String passed to it as an argument, as shown in Table 3.1.
TABLE 3.1 Operation of the compareTo() Method
|
s2.compareTo(s1) |
Return Value |
|
s1 < s2 |
< 0 |
|
s1 equals s2 |
0 |
|
s1 > s2 |
> 0 |
For example, if s1 is "cat" and s2 is "dog", the function will return a number less than 0. In the objectSort.java program, this method is used to compare the last name of a[in-1] with the last name of temp.
Stability
Sometimes it matters what happens to data items that have equal keys. For example, you may have employee data arranged alphabetically by last names. (That is, the last names were used as key values in the sort.) Now you want to sort the data by ZIP code, but you want all the items with the same ZIP code to continue to be sorted by last names. You want the algorithm to sort only what needs to be sorted, and leave everything else in its original order. Some sorting algorithms retain this secondary ordering; they're said to be stable.
All the algorithms in this chapter are stable. For example, notice the output of the objectSort.java program (Listing 3.4). Three persons have the last name of Smith. Initially, the order is Doc Smith, Lorraine Smith, and Paul Smith. After the sort, this ordering is preserved, despite the fact that the various Smith objects have been moved to new locations.