Java Sort Arrays Examples (with Comparable and Comparator)

This tutorial helps you how to use the Arrays utility class to sort elements in an array.

You know, the java.util.Arrays class provides various methods for sorting elements of an array, as simple as:

Arrays.sort(array)

This tutorial shows various examples of sorting an array using such methods, especially using the Comparable and Comparator interfaces. But first, let’s look at the implementation details of sorting algorithms in JDK.

The sorting algorithms in JDK

For primitive arrays, a tuned version of Quicksort algorithm is used (in JDK 6 and previous versions) or Dual-Pivot Quicksort is used (in JDK 7 and later versions). Both algorithms offers O(n log(n)) performance but the Dual-Pivot Quicksort is typically faster.

For Object arrays, a modified version of Mergesort algorithm is used. It is slightly optimized to be fast and stable, i.e. it offers O(n log n) performance in average and worst cases; runs faster if the array is partially sorted; and it won’t re-order equal elements.

1. Sorting an array of primitives

The following example shows how easy it is to sort an array of primitives (e.g. integer numbers):

int[] numbers = {4, 9, 1, 3, 2, 8, 7, 0, 6, 5};
java.util.Arrays.sort(numbers);

Putting two System.out.println() statements to print the array’s elements before and after sorting:

int[] numbers = {4, 9, 1, 3, 2, 8, 7, 0, 6, 5};

System.out.println(Arrays.toString(numbers));

java.util.Arrays.sort(numbers);

System.out.println(Arrays.toString(numbers));

Output:

Before sorting: [4, 9, 1, 3, 2, 8, 7, 0, 6, 5]
After sorting: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Similarly for other primitive types (byte, char, short, long, float, and double) by using the appropriate methods:

Arrays.sort(long[] a)
Arrays.sort(float[] a)
Arrays.sort(double[] a)
Arrays.sort(char[] a)
Arrays.sort(byte[] a)
Arrays.sort(short[] a)

2. Sorting an array of Objects

Suppose that we have an array of custom objects of type Employee:

public class Employee {
	private String name;
	private int age;
	private int salary;

	public Employee(String name, int age, int salary) {
		this.name = name;
		this.age = age;
		this.salary = salary;
	}

	// getters and setters...
}

Now, we want to sort all employees in the array by their salary field in ascending order. To do so, it requires the Employee class to implement the Comparable interface and override the compareTo() method as follows:

public class Employee implements Comparable<Employee> {
	// variables
	// constructor
	// getters and setters

	@Override
	public int compareTo(Employee employee) {
		return this.salary - employee.salary;
	}
}

The reason is that, the Arrays.sort(Object[]) method requires the object type to implement the Comparable interface so that the array can be sorted according to natural ordering of its elements. The natural ordering is defined by implementation of the compareTo() method which determines how the current object (obj1) is compared to another (obj2) of the same type. The order is based on return value (an integer number, say x) of the compareTo() method:

• obj1 > obj2 if x > 0.
• obj1 < obj2 if x < 0.
• obj1 equals obj2 if x = 0.

And here’s the code that demonstrates how the array is sorted:

Employee[] employees = new Employee[4];

employees[0] = new Employee("Tom", 45, 80000);
employees[1] = new Employee("Sam", 56, 75000);
employees[2] = new Employee("Alex", 30, 120000);
employees[3] = new Employee("Peter", 25, 60000);

System.out.println("Before sorting: " + Arrays.toString(employees));

Arrays.sort(employees);

System.out.println("After sorting: " + Arrays.toString(employees));

Putting the following toString() method to the Employee class:

public String toString() {
	return String.format("(%s, %d)", name, salary);
}

Therefore we have the following output (the number after the name indicates the salary):

Before sorting: [(Tom, 80000), (Sam, 75000), (Alex, 120000), (Peter, 60000)]
After sorting: [(Peter, 60000), (Sam, 75000), (Tom, 80000), (Alex, 120000)]

What if the Employee class doesn’t implement the Comparable interface? In that case, the Arrays.sort() method will throw a java.lang.ClassCastException at runtime, for example:

Exception in thread "main" java.lang.ClassCastException: Employee cannot be cast to java.lang.Comparable

What if, for some reasons, we cannot make the Employee class implements the Comparable interface (e.g. lacking of source code, or the array needs to be sorted into different order)? In that case, look at the next section on using a Comparator.

NOTES: Some core classes in the JDK already implemented the Comparable interface (e.g. String, Date and primitive wrappers: Integer, Long, Double, etc), so that we can sort array of these types naturally. Here are some examples:

• Sorting an array of Strings:

  String[] fruits = {"Orange", "Grape", "Apple", "Lemon", "Banana"};
  
  System.out.println("Before sorting: " + Arrays.toString(fruits));
  
  Arrays.sort(fruits);
  
  System.out.println("After sorting: " + Arrays.toString(fruits));

  Output:

  Before sorting: [Orange, Grape, Apple, Lemon, Banana]
  After sorting: [Apple, Banana, Grape, Lemon, Orange]

• Sorting an array of Dates:

  Date[] dates = new Date[3];
  DateFormat dateFormatter = new SimpleDateFormat("yyyy-MM-dd");
  
  try {
  	dates[0] = dateFormatter.parse("2013-09-30");
  	dates[1] = dateFormatter.parse("2013-07-06");
  	dates[2] = dateFormatter.parse("2013-11-28");
  } catch (ParseException ex) {
  	System.err.print(ex);
  }
  
  System.out.println("Before sorting: " + Arrays.toString(dates));
  
  Arrays.sort(dates);
  
  System.out.println("After sorting: " + Arrays.toString(dates));

  Output:

  Before sorting: [Mon Sep 30 00:00:00 ICT 2013, Sat Jul 06 00:00:00 ICT 2013, Thu Nov 28 00:00:00 ICT 2013]
  After sorting: [Sat Jul 06 00:00:00 ICT 2013, Mon Sep 30 00:00:00 ICT 2013, Thu Nov 28 00:00:00 ICT 2013]

Consistency with equals() method

It’s strongly recommended that implementation of the compareTo() method of a class must be consistent with its equals() method when the objects are used in sorted maps or sorted sets. That means obj1.compareTo(obj2) == 0 must have same boolean value as obj1.equals(obj2) for every obj1 and obj2 of a particular class. Otherwise, the sorted maps or sorted sets will behave strangely. Because this tutorial doesn’t deal with sorted maps or sorted sets, so we don’t implement equals() method for the Employee class in the examples.

3. Sorting an array of Objects using a Comparator

Besides using the Comparable implementation approach, it’s also possible to sort an array of Objects by passing an implementation of the java.util.Comparator interface to the Arrays.sort() method:

Arrays.sort(array, comparator)

The Comparator interface defines a compare() method that imposes a total ordering on some collection of objects. Its purpose is similar to the Comparable’s compareTo() method, but is independent of the objects being compared. For example, the following comparator does the same thing as the Employee’s compareTo() method above:

package net.codejava.arrays;

import java.util.Comparator;

/**
 * This comparator compares two employees by their salaries (lower first).
 * @author www.codejava.net
 *
 */
public class EmployeeSalaryComparator implements Comparator<Employee> {

	@Override
	public int compare(Employee emp1, Employee emp2) {
		return emp1.getSalary() - emp2.getSalary();
	}
}

And pass this comparator to the Arrays.sort() method as follows:

Arrays.sort(employees, new EmployeeSalaryComparator());

Here is an example with some dummy data:

Employee[] newEmployees = new Employee[4];

newEmployees[0] = new Employee("Tom", 45, 80000);
newEmployees[1] = new Employee("Sam", 56, 75000);
newEmployees[2] = new Employee("Alex", 30, 120000);
newEmployees[3] = new Employee("Peter", 25, 60000);

System.out.println("Before sorting: " + Arrays.toString(newEmployees));

Arrays.sort(newEmployees, new EmployeeSalaryComparator());

System.out.println("After sorting: " + Arrays.toString(newEmployees));

Output:

Before sorting: [(Tom, 80000), (Sam, 75000), (Alex, 120000), (Peter, 60000)]
After sorting: [(Peter, 60000), (Sam, 75000), (Tom, 80000), (Alex, 120000)]

As you can see, this sort result is same as the result of implementing the Comparable interface. But using a Comparator, we don’t need to make the Employee class implements the Comparable interface, because the objects ordering is imposed by the comparator itself, not by the objects being compared. In addition, we can create another comparator to sort the array on different fields when needed. For example, the following comparator will sort the employees by their ages in ascending order:

package net.codejava.arrays;

import java.util.Comparator;

/**
 * This comparator compares two employees by their ages (younger first).
 * @author www.codejava.net
 *
 */
public class EmployeeAgeComparator implements Comparator<Employee> {

	@Override
	public int compare(Employee emp1, Employee emp2) {
		return emp1.getAge() - emp2.getAge();
	}
}

It’s also common to create the comparator as an anonymous class which is passed directly into the Arrays.sort() method. For example, the following code sorts the array by the employee’s names:

Arrays.sort(newEmployees, new Comparator<Employee>() {
	@Override
	public int compare(Employee emp1, Employee emp2) {
		return emp1.getName().compareTo(emp2.getName());
	}
});

Furthermore, using the Comparator, we can manipulate complex sorting conditions, e.g. sorting on multiple attributes of the objects. For more information, see: Sorting a list by multiple attributes example.

4. Sorting an array into reverse order

To sort an array of objects into the reverse of natural ordering of its elements, we can use this syntax:

Arrays.sort(array, Collections.reverseOrder());

The Collections.reverseOrder() static method returns a Comparator object that imposes the reverse of natural ordering on a collection of objects that implement the Comparable interface. For example, the following code sorts an array of Strings into the alphabetical order, then into the reverse:

String[] fruits = {"Orange", "Grape", "Apple", "Lemon", "Banana"};

Arrays.sort(fruits);
System.out.println("Alphabetical order: " + Arrays.toString(fruits));

Arrays.sort(fruits, Collections.reverseOrder());
System.out.println("Reverse-alphabetical order: " + Arrays.toString(fruits));

Output:

Alphabetical order: [Apple, Banana, Grape, Lemon, Orange]
Reverse-alphabetical order: [Orange, Lemon, Grape, Banana, Apple]

What about the reverse order of a specific Comparator (which imposes the total ordering, not the natural ordering)? Well, the Collections class also provides the following method:

Comparator<T> reverseOrder(Comparator<T> cmp)

This method returns a comparator that imposes the reverse ordering of the specified comparator. For example, we can get a comparator which is a reverse of the EmployeSalaryComparator as follows:

Comparator<Employee> descendingSalaryComparator = Collections.reverseOrder(new EmployeeSalaryComparator());

And use this comparator:

Arrays.sort(newEmployees, descendingSalaryComparator);

System.out.println("Sort by descending salary: " + Arrays.toString(newEmployees));

Output:

Sort by descending salary: [(Alex, 120000), (Tom, 80000), (Sam, 75000), (Peter, 60000)]

For arrays of primitives, there is no direct way to sort them in the reverse of natural ordering. Instead, we must convert an array of primitives to an array of corresponding wrapper objects (e.g. int to Integer), and then apply the technique above.

5. Sorting a specified range of an array

The Arrays class provides some convenient methods for sorting a specified range of an array as follows:

Arrays.sort(array, int fromIndex, int toIndex)
Arrays.sort(array, int fromIndex, int toIndex, comparator)

The range is specified within from the fromIndex (inclusive) to the toIndex (exclusive). The following example sorts only a half of an array of ten integer numbers:

int[] numbers = {4, 9, 1, 3, 2, 8, 7, 0, 6, 5};

System.out.println("Before sorting: " + Arrays.toString(numbers));

Arrays.sort(numbers, 0, 5);

System.out.println("Sorted a half: " + Arrays.toString(numbers));

Output:

Before sorting: [4, 9, 1, 3, 2, 8, 7, 0, 6, 5]
Sorted a half: [1, 2, 3, 4, 9, 8, 7, 0, 6, 5]

And the following example sorts just 3 employees based on their ages, using a comparator:

Arrays.sort(newEmployees, 0, 3, new EmployeeAgeComparator());

6. Conclusion

So far we have gone through examples of sorting arrays using various variants of the java.util.Arrays.sort() method, including usages of the Comparable and Comparator interfaces. Key points to remember are:

• The Comparable interface imposes the natural ordering of an object, through contract of the compareTo() method.
• The Comparator interface imposes the total ordering of on some collection of objects, through contract of the compare() method.
• The Arrays.sort(objectArray) method only works with a collection of objects that implement the Comparable interface, i.e. have natural ordering.

API References

• Object Ordering
• Comparable interface Javadoc
• Comparator interface Javadoc
• java.util.Arrays class Javadoc

Related Sorting tutorials:

• Java Sort a list by multiple attributes example
  
• Sorting List Collections Examples

Other Java Collections Tutorials:

• Java Set Tutorial
• Java Map  Tutorial
• Java List Tutorial and
• Java Queue Tutorial
• Understanding equals() and hashCode() in Java
• Understanding Object Ordering in Java with Comparable and Comparator
• 18 Java Collections and Generics Best Practices

About the Author:

Nam Ha Minh is certified Java programmer (SCJP and SCWCD). He began programming with Java back in the days of Java 1.4 and has been passionate about it ever since. You can connect with him on Facebook and watch his Java videos on YouTube.

Attachments:

ArraysSortingExamples.zip

[Java source files]

9 kB