Home > Articles > Programming > Java

  • Print
  • + Share This
  • 💬 Discuss

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.

  • + Share This
  • 🔖 Save To Your Account

Discussions

comments powered by Disqus