Java Interviews – What is the difference between the Comparable and Comparator interfaces?

Sorting Lists

A common operation on collections—lists in particular—is to rearrange the list into some kind of sorted order. Lists are often sorted using natural ordering, such as sorting numbers from lowest to highest or sorting characters into alphabetical order. However, you may have different requirements for your sorting. Java provides two interfaces for helping with sorting:

Comparable

and

Comparator

.


What is the difference between the

Comparable

and

Comparator

interfaces?


Because these interfaces are public, they can be put to any use. By convention, the

Comparable

interface is used for natural ordering, and

Comparator

is used to give exact control over the ordering.

When sorting an array, you generally use a built-in library, such as the implementation included in the

Arrays

and

Collections

classes. However, for an interview you may be asked to write your own implementation.

The

Arrays

and

Collections

classes have several overloaded

sort

methods, which can broadly be split into two: one that takes an array as a parameter, and one that takes an array and a

Comparator

object. The method is overloaded for each of the primitive types and one for the reference type (

Object

).

For the implementation without a

Comparator

object, the type is sorted by its natural ordering. Listing 1 shows this for

int

s, sorting the array from low to high.

Listing 1: Naturally sorting an array of ints


@Test
public void sortInts() {
    final int[] numbers = {-3, -5, 1, 7, 4, -2};
    final int[] expected = {-5, -3, -2, 1, 4, 7};

    Arrays.sort(numbers);
    assertArrayEquals(expected, numbers);
}

For an array of

Object

s, the type being sorted must implement the

Comparable

interface, as shown in Listing 2.

Listing 2: Sorting objects naturally


@Test
public void sortObjects() {
    final String[] strings = {"z", "x", "y", "abc", "zzz", "zazzy"};
    final String[] expected = {"abc", "x", "y", "z", "zazzy", "zzz"};

    Arrays.sort(strings);
    assertArrayEquals(expected, strings);
}

The

String

class implements the

Comparable

interface, so the sorting works as you would expect. If the type being sorted does not implement

Comparable

, this will throw a

ClassCastException

.

For your own class definitions, you will need to implement

Comparable

, such as the implementation described in Listing 3.

Listing 3: Sorting without a Comparable interface


private static class NotComparable {
    private int i;
    private NotComparable(final int i) {
        this.i = i;
    }
}

@Test
public void sortNotComparable() {
    final List<NotComparable> objects = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        objects.add(new NotComparable(i));
    }

    try {
        Arrays.sort(objects.toArray());
    } catch (Exception e) {
        // correct behavior – cannot sort
        return;
    }

    fail();
}

It is not possible to use the

Collections.sort

method because the compiler expects the type of the parameter to be an implementation of

Comparable

. The method signature is:


public static <T extends Comparable<? super T>> void sort(List<T> list)

If you want to provide your own ordering, you provide an implementation of the

Comparator

interface to the

sort

method. This interface has two methods:

int compare(T o1, T o2)

for the implementing type

T

, and

boolean equals(Object o)

. The

compare

method returns an

int

in one of three states: negative if the first argument is sorted before the second, zero if the two are equal, or positive if the second argument is sorted first.

If you were to provide a reverse numerical order

Comparator

, the implementation may look like Listing 4.

Listing 4: A reverse numerical order Comparator


public class ReverseNumericalOrder implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
    // equals omitted
}

Listing 5 uses this

Comparator

.

Listing 5: Using a custom ordering


@Test
public void customSorting() {
    final List<Integer> numbers = Arrays.asList(4, 7, 1, 6, 3, 5, 4);
    final List<Integer> expected = Arrays.asList(7, 6, 5, 4, 4, 3, 1);

    Collections.sort(numbers, new ReverseNumericalOrder());
    assertEquals(expected, numbers);
}

This article is excerpted from Wrox’s Java Programming Interviews Exposed (ISBN: 978-1-118-72286-2, copyright 2014 John Wiley & Sons) by Noel Markham. Some of the other Java interview list sorting questions answered in chapter 4 include:

  • How would you implement a bubble sort algorithm?
  • How would you implement the insert sort algorithm?
  • How would you implement the quicksort algorithm?
  • How would you implement the merge sort algorithm?

Noel Markham is a developer with almost 15 years’ experience using Java across financial, technology, and gaming industries. Most recently, he has been working for startups in social gaming and digital entertainment. He has hosted interviews for all experienced levels of developer, from graduates to technical leaders, and has set up assessment centers in the UK and overseas to set up full development teams.

Tags:

Comments

One response to “Java Interviews – What is the difference between the Comparable and Comparator interfaces?”

  1. Vasily says:

    Dear Jim,
    What was your reason to use final qualifier
    in Listing 5?

    final List numbers = …

    Sincerely,

    Vasily.

Leave a Reply to Vasily Cancel reply

Your email address will not be published. Required fields are marked *