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 JDKFor 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.int[] numbers = {4, 9, 1, 3, 2, 8, 7, 0, 6, 5}; java.util.Arrays.sort(numbers);
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)
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:
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.ComparableWhat 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:
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]
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]
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.
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.
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());