≡ Menu

Sorting Collections in Java

arraylist sorting in Java ProgrammingHave you run into a situation where you had a Collection of Objects (or an Array), and you needed to have them ordered in a certain way?

Chances are that if you’ve been programming with Java and running through the assignments available on this blog, then you have. So how can this be done? And moreover, how can this be done in a way that’s fully customizable?

Comparator/Comparable Interfaces

Enter the Comparator and Comparable interfaces… these are what we use to accomplish the sorting of Collections and Arrays in a customizable way. You might ask “Why are there two different interfaces used for sorting?”. That’s a great question, and I’ll answer it soon.

So let’s start off with a simple example so that you have a clear understanding of what I’m talking about. Let’s assume you’re presented with the following ArrayList:

[I, , L, O, V, E, , J, A, V, A, , P, R, O, G, R, A, M, S]

With this ArrayList, let’s say you’re given the requirements to sort all of the letters in a unique way.

  1. You first need to show all of the vowels first (in alphabetical order)
  2. Then then you need to list all the consonants after the vowels (also in alphabetical order)

The resulting ArrayList should look like this:

[A, A, A, E, I, O, O, , , , G, J, L, M, P, R, R, S, V, V]

How Would You Solve this Problem?

Well, if you just tried to use the standard Collections.sort(theArrayList), it wouldn’t get you very far. The static sort method of the Collections Class that takes a List will just arrange the letters alphabetically and it won’t put all the vowels first.

So you’ll need to use a customized sorting algorithm, which means picking between either the Comparable or Comparator interfaces. So how in the world do you pick between them?

Well just keep in mind that they both do the same thing in the end. They will both allow you to define a custom sorting algorithm for your Objects.

Comparator

  • Use this interface if you want to custom sort on an Object type that you didn’t create (i.e. Character, Integer, String)
  • This interface is used to compare two different instances of an Object
  • It uses the compare(Object object1, Object object2) method to perform its magic

Comparable

  • Use this interface if you want to custom sort an Object that you have created (i.e. Users, HumanBeing, Vehicle, Car etc.)
  • This interface is used to compare the current instance of your Object to another one (i.e. Compare this instance of HumanBeing to another HumanBeing)
  • It uses the compareTo(Object anotherObjectOfSameType) method to perform its magic

Let’s Solve our Problem

Okay, so given the information above, and knowing that we want to sort an ArrayList do you know which one of the interfaces you would use?

Seriously, I want you to figure it out. Don’t read anything else until you have come up with a guess in your mind.

No cheating…

Well, since we are trying to sort an ArrayList of Strings then we will need to use the Comparator. So let’s have a look at the code and how this can be made possible, here’s the example of how to do a regular old sort of an ArrayList:

public class SortingExample
{
  public static void main(String[] args)
  {
    // instantiate ArrayList
    List theArrayList = new ArrayList();

    // construct the ArrayList with our letters
    theArrayList.add("I");theArrayList.add(" ");
    theArrayList.add("L");theArrayList.add("O");theArrayList.add("V");theArrayList.add("E");theArrayList.add(" ");
    theArrayList.add("J");theArrayList.add("A");theArrayList.add("V");theArrayList.add("A");theArrayList.add(" ");
    theArrayList.add("P");theArrayList.add("R");theArrayList.add("O");theArrayList.add("G");
    theArrayList.add("R");theArrayList.add("A");theArrayList.add("M");theArrayList.add("S");

    Collections.sort(theArrayList);
  }
}

So you see here that we’re populating an ArrayList with our “test” sentence and then we invoke the Collections.sort() method. The resulting ArrayList would look like this:

[ , , , A, A, A, E, G, I, J, L, M, O, O, P, R, R, S, V, V]

As you can see, that’s not what we’re looking for; we want all the vowels to appear first. So let’s get on with the good code where we make use of our Comparator. If you study the Collections.sort() methods, you’ll see that there’s one that takes two parameters, a List and a Comparator, so this is the method we’re interested in using.

I’m going to be making use of something called an Anonymous Inner Type. It’s kind of like creating a whole class that can be used within an existing method. It has a special notation, so if you don’t quite get it, no worries:

Collections.sort(theArrayList, new Comparator()
{
  @Override
  public int compare(String o1, String o2)
  {
    if (isVowel(o1) && !isVowel(o2))
    {
      return -1;
    }
    else if (!isVowel(o1) && isVowel(o2))
    {
      return 1;
    }
    
    return o1.toLowerCase().compareTo(o2.toLowerCase());
  }

  /**
  * This method determine if the String being passed in is a vowel or not.
  * @param o1 the String that may or may not be a vowel
  * @return true if the letter is a vowel, false otherwise
  */
  private boolean isVowel(String o1)
  {
    return o1.equalsIgnoreCase("a") || o1.equalsIgnoreCase("e") || o1.equalsIgnoreCase("i")
        || o1.equalsIgnoreCase("o") || o1.equalsIgnoreCase("u");
  }
});

Alright, so you see here that we are using a Comparator inside of the Collections.sort() method. But we’re doing something neat, we’re declaring an anonymous inner type for this Comparator. What I’m doing here is I’m avoiding having to create a whole new Object, then have that Object implement the Comparator interface, then @Override the appropriate compare(String o1, String o2) method, then instantiate that Object and pass it into the Collections.sort() method.

I have avoided all of this pain and suffering by using this little anonymous inner type trick. You’ll notice that when I instantiate a new Comparator via new Comparator() I also immediately insert an open curly brace ({). This tells Java that I’m creating an anonymous inner type. If you stop to think about it, you’re not allowed to instantiate an interface right? Right! But you can use this trick to get around all that pain I described above.

So! Having explained that, let’s talk about that compare() method.

Comparator’s compare(Object o1, Object o2) Method

This method is where the real magic happens in the sorting process. It’s a bit confusing, so try and stick with me on this. When sorting through anything, Java will constantly compare one object to another object (often more than 1 time per Object).

Here’s a quick video explanation of one sorting process called the “Bubble sort”:

So as you heard in the video above, the compare(Object o1, Object o2) method is the key to doing the sorting, and it works by returning an int. Now as I said in the video, this method returns one of three values:

  • negative number – if first argument is less than the second
  • 0 – first argument is equal to the second
  • positive number – if first argument is greater than the second

Based on these return values, Java will be able to properly sort your Collection. It will be able to do this by “swapping” the values around appropriately. If you’re interested in learning more about the specific algorithm Java uses when you invoke Collections.sort(), then read up on Merge Sort. If you don’t want to read the article, then here’s an awesome animated “explanation” on how Merge Sort works (just click on it to ‘restart’ the animation):

java sort arraylistMerge-sort-example-300px

Okay, so that about wraps up this post… as always, if you really enjoy my teaching style and want to get on the fast track for learning Java, head over to Java Video Tutorials and read up about my fantastic video course. The students currently enrolled in the course have had nothing but great things to say about it, and I’m so excited to be making a real difference in their journey to become programmers.

{ 1 comment… add one }

  • Akash November 26, 2013, 8:39 am

    Hi Trevor ,

    I am not clear with this comparator and comparable.
    Can you please gives some more explaination on this topic , may be if can use some examples for both would be easy to understand.

    Thanks in Advance

Leave a Comment