Select Page

# Sorting Collections in Java

Have 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 `Collection`s and `Array`s 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 `String`s 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

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):

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.