Insertion sort with an array of objects?

Question

I have an array of Faculty members and I want to use the Insertion Sort on it. I get an error at:

InsertionSort.insertionSortA(faculty, faculty.length);

The error says : "Method insertionSortA in class InsertionSort cannot be applied to given types;
required: Comparable [], int
found: Faculty [], int
I know that doing this will not work:

InsertionSort.insertionSortA((Comparable[]) faculty, faculty.length);

I know that if I had an Integer[] array would work, but I'm confused why my Faculty[] would not work?

public class Tester {

public static void main(String[] args) {

    InsertionSort insertionSort = new InsertionSort();
    Education edu = new Education ("BA", "Business", 1);
    Education edu2 = new Education ("BA", "Health Science", 1);
    Education edu3 = new Education ("BA", "Computer Science", 1);

    Faculty[] faculty  = new Faculty[] { 

    new Faculty ("538", "Doe", "Jane", 'M', 1994,1,10, 
     "Assistant", edu),
    new Faculty ("238", "Do", "John", 'F', 1994,6,1, 
     "Assistant", edu2),
    new Faculty ("080", "White", "Snow", 'F', 1994,4,22, 
     "Full", edu3)
    };

    InsertionSort.insertionSortA(faculty, faculty.length);
}

}

public class InsertionSort {

public static void insertionSortA(Comparable[] theArray, int n) {

    for (int unsorted = 1; unsorted < n; ++unsorted) {
        Comparable nextItem = theArray[unsorted];
        int loc = unsorted;
        while ((loc > 0) &&(theArray[loc-1].compareTo(nextItem) > 0)) {
            theArray[loc] = theArray[loc-1];
            loc--;
        } // end while
        theArray[loc] = nextItem;
    } // end for
} // end insertionSort
public static void insertionSortB(Comparable[] theArray, int n) {

    for (int unsorted = 1; unsorted < n; ++unsorted) {
        Comparable nextItem = theArray[unsorted];
        int loc = unsorted;
        while ((loc > 0) &&(theArray[loc-1].compareTo(nextItem) < 0)) {
            theArray[loc] = theArray[loc-1];
            loc--;
        } // end while
        theArray[loc] = nextItem;
    } // end for
} 
}

Answer 1

In order to apply insertion sort on your array/collection the elements need to be comparable (Comparison logic is on the basis of how you want to compare 2 faculty members, can be on the basis of name, age, salary etc). This can be done by implementing the interface Comparable in Faculty class and defining the function compareTo() as follows :

public class Faculty implements Comparable<Faculty>
{
   public int compareTo(Faculty f)
   {

   // comparison logic is on the basis of how you want to compare 2 faculty members 
   //  you might want to compare name, salaries etc

   }
}

compareTo() function must return the following :

 zero             : If object is same as the specified object (f)
 positive integer : If object is greater than the specified object (f)
 negative integer : If object is less than the specified object (f)

Refer the documentation at the following link

Answer 2

Without seeing the Faculty class, we can only guess at your problem.

It seems that Faculty does not implement Comparable. You can call the function with an Integer[], because Integer is comparable--it does implement Comparable.

You'll need to implement Comparable<Faculty> in your Faculty class, by overriding compareTo(Faculty)

public int compareTo(Faculty faculty)  {
    //...
}

As far as what this should return, you should review its API. But in general, if they're exactly equal, return 0, if this is greater than faculty (whatever you define "greater" to mean), it should return something greater than 0. There aren't any strict rules beyond this, aside from it always returning a consistent value.

Answer 3

For those still stumbling across this page, an alternative solution would be to disregard the Comparable interface. Since there are a lot of situations when an object could be sorted by more than one attribute, e.g., id, first name, last name, or start year. In this case, you would create separate methods for each sort attribute in the InsertionSort class. This would also require you to change the sort methods input parameter type from Comparable[] to Faculty[].

public class InsertionSort {

  public static void byLastName(Faculty[] theArray, int n) {

    for (int unsorted = 1; unsorted < n; ++unsorted) {
      Faculty nextItem = theArray[unsorted];
      int loc = unsorted;
      while ((loc > 0) &&(theArray[loc-1].getLastName().compareTo(nextItem.getLastName()) > 0)) {
        theArray[loc] = theArray[loc-1];
        loc--;
      } 
      theArray[loc] = nextItem;
    }
  }

  public static void byFirstName(Faculty[] theArray, int n) {

    for (int unsorted = 1; unsorted < n; ++unsorted) {
      Faculty nextItem = theArray[unsorted];
      int loc = unsorted;
      while ((loc > 0) &&(theArray[loc-1].getFirstName().compareTo(nextItem.getFirstName()) > 0)) {
        theArray[loc] = theArray[loc-1];
        loc--;
      } 
      theArray[loc] = nextItem;
    }
  }
}

You could then sort your Faculty array like this:

InsertionSort.byLastName(faculty, faculty.length);

OR

InsertionSort.byFirstName(faculty, faculty.length);

For a more detailed explanation on sorting objects with Insertion Sort check out my blogpost. It has implementations in Java, C++, Python, and Javascript.