Sorting in Java
- An array of primitive types like
byte,short,int,long,float,double,char,booleancan be sorted by calling the overloaded static methodjava.util.Arrays.sort(<primitive-type>[] arr) - An array of wrapper types/Value Objects like
Byte,Short,Integer,Long,Float,Double,Character,Booleancan be sorted by calling thejava.util.Arrays.sort(Object[] arr)overloaded version of static method. Also, we can sort user-defined objects like Employee by callingjava.util.Arrays.sort(Object[] arr)provided the class should implementjava.lang.Comparable<T>interface.
Brief of java.lang.Comparable interface in java
public interface Comparable<T> {
public int compareTo(T o);
}
Javadoc of java.lang.Comparable interface
This interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class’s natural ordering, and the class’s compareTo method is referred to as its natural comparison method.
The natural ordering for a class C is said to be consistent with equals if and only if e1.compareTo(e2) == 0 has the same boolean value as e1.equals(e2) for every e1 and e2 of class C. Note that null is not an instance of any class, and e.compareTo(null) should throw a NullPointerException even though e.equals(null) returns false.
Here is the javadoc excerpt of java.lang.Comparable interface’s compareTo(T o) method
Compares this object with the specified object for order. Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.
Brief overview of java.util.Arrays util class and its static factory methods. Out of all the methods, there are 2 handy methods
public static String toString(T[] t) // to print arraypublic static void sort(T[] t) // to sort the array
Printing array
Example to print the int[] in Java
// we can't get the array printed with the following line
java.lang.System.out.println(ints);// assume ints is of type int[]
System.out.println("Printing the array of ints " + Arrays.toString(ints));
Here is the list of overloaded public static String toString() methods
public static String toString(byte[] arr) { /*impl code*/ }
public static String toString(short[] arr) { /*impl code*/ }
public static String toString(int[] arr) { /*impl code*/ }
public static String toString(long[] arr) { /*impl code*/ }
public static String toString(float[] arr) { /*impl code*/ }
public static String toString(double[] arr) { /*impl code*/ }
public static String toString(char[] arr) { /*impl code*/ }
public static String toString(boolean[] arr) { /*impl code*/ }
// For wrappers/VOs like Byte, Short, Integer, Long, Float, Double, Boolean, and Character and objects like String etc, or user defined objects
public static String toString(Object[] arr) { /*impl code*/ }
Use Arrays.deepToString(deepArray) to print multidimensional arrays.
Example:
String[][] deepArray = new String[][] {
{"John", "Mary"},
{"Alice", "Bob"}
};
System.out.println(Arrays.deepToString(deepArray)); // Prints: [[John, Mary], [Alice, Bob]]
Sorting array
Example to sort the int[] in Java
int[] ints = new int[]{99,1,3};
System.out.println("Sorted ints = " + java.util.Arrays.sort(ints));
// prints [1,3,9]
Here is the excerpt from the javadoc of Arrays.sort(<primitve>[] arr) method
Sorts the specified array into ascending numerical order.
Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.
Here is the list of overloaded public static void sort(T[] t) methods
public static void sort(byte[] arr) { /* impl code */ }
public static void sort(short[] arr) { /* impl code */ }
public static void sort(int[] arr) { /* impl code */ }
public static void sort(long[] arr) { /* impl code */ }
public static void sort(float[] arr) { /* impl code */ }
public static void sort(double[] arr) { /* impl code */ }
public static void sort(char[] arr) { /* impl code */ }
public static void sort(boolean[] arr) { /* impl code */ }
// For wrappers/VOs like Byte, Short, Integer, Long, Float, Double, Boolean, and Character and objects like String etc, or user defined objects
public static void sort(Object[] arr) { /* impl code */ }
Here is the javadoc for Arrays.sort(Object[] arr)
Sorts the specified array of objects into ascending order, according to the natural ordering of its elements. All elements in the array must implement the Comparable interface. Furthermore, all elements in the array must be mutually comparable (that is, e1.compareTo(e2) must not throw a ClassCastException for any elements e1 and e2 in the array).
This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.
Implementation note: This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n log(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.
The implementation takes equal advantage of ascending and descending order in its input array, and can take advantage of ascending and descending order in different parts of the same input array. It is well-suited to merging two or more sorted arrays: simply concatenate the arrays and sort the resulting array.
The implementation was adapted from Tim Peters’s list sort for Python ( TimSort). It uses techniques from Peter McIlroy’s “Optimistic Sorting and Information Theoretic Complexity”, in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993.
All the wrappers/VOs classes like Byte, Short, Integer, Long, Float, Double, Character, Boolean will work with Arrays.sort(Object[] arr)
Why? Because all the wrappers/VOs implement java.lang.Comparable<T> interface and override public int compareTo(T t){ /* impl code */ }
Sorting array with fromIndex(Inclusive), toIndex(Exclusive)
Another overloaded static method of sort is
public static void sort(byte[] arr, int fromIndex, int toIndex) { /* impl code */ }
Here is javadoc excerpt for
Arrays.sort(<primitve>[] arr, int fromIndex, int toIndex){}
Sorts the specified range of the array into ascending order. The range to be sorted extends from the index fromIndex, inclusive, to the index toIndex, exclusive. If fromIndex == toIndex, the range to be sorted is empty.
Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.
Here is the list of all overloaded static methods of sort(T[], int fromIndex, int toIndex)
public static void sort(byte[] arr, int fromIndex, int toIndex) { /* impl code */}
public static void sort(short[] arr, int fromIndex, int toIndex) { /* impl code */ }
public static void sort(int[] arr, int fromIndex, int toIndex) { /* impl code */ }
public static void sort(long[] arr, int fromIndex, int toIndex) { /* impl code */ }
public static void sort(float[] arr, int fromIndex, int toIndex) { /* impl code */ }
public static void sort(double[] arr, int fromIndex, int toIndex) { /* impl code */ }
public static void sort(char[] arr, int fromIndex, int toIndex) { /* impl code */ }
public static void sort(boolean[] arr, int fromIndex, int toIndex) { /* impl code */ }
// For wrappers/VOs like Byte, Short, Integer, Long, Float, Double, Boolean, and Character and objects like String etc, or user defined objects
public static void sort(Object[] arr, int fromIndex, int toIndex) { /* impl code */ }
Sorting and Printing java.lang.String[]
Like all Wrappers/VO’s, java.lang.String class also implements Comparable<T> interface
public final class String implements
java.io.Serializable, Comparable<String>, CharSequence {
/* impl code */
}
Hence, we can sort String[] calling java.util.Arrays.sort(Object[] arr) method
Example:
String[] fruits = {"grape", "apple", "banana"};
java.util.Arrays.sort(fruits); // sorts the String[] in natural order
System.out.println(Arrays.toString(fruits));
// Prints [apple, banana, grape]
Sorting user-defined objects
Any user defined object say Emmployee which doesn’t implement java.lang.Comparable cannot be sorted using Array.sort(Object[] arr) it will throw java.lang.ClassCastException
Example:
class Employee {
private int id;
private String name;
public Employee(int id, String name) {
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public String getName() {
return name;
}
}
class Demo {
public static void main(String[] args) {
Employee[] employees = new Employee[3];
employees[0] = new Employee(99, "srk");
employees[1] = new Employee(2, "hero");
employees[2] = new Employee(6, "godman");
java.util.Arrays.sort(employees); // Will it work?
}
}
It will throw java.lang.ClassCastException: class Employee cannot be cast to java.lang.Comparable
Here is the fix
class Employee implements java.lang.Comparable<Employee>{
private int id;
private String name;
public Employee(int id, String name) {
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public String getName() {
return name;
}
@Override
public int compareTo(Employee employee) {
return this.id - employee.id;
/*-
* Note:
* For ascending order/Natural order: return this.id - employee.id;
* For descending order/Reverse order: return employee.id - this.id;
*
* returns 0 - when this object's id is equal to specified object
* returns -1 - when this object's id is less than specified object
* returns 1 - when this object's id is greater than specified object
*/
}
@Override
public String toString() {
return "id = " + id + " name = " + name;
}
}
class Demo {
public static void main(String[] args) {
Employee[] employees = new Employee[3];
employees[0] = new Employee(99, "srk");
employees[1] = new Employee(2, "hero");
employees[2] = new Employee(6, "godman");
java.util.Arrays.sort(employees);
System.out.println(Arrays.toString(employees));
// Prints
// [id = 2 name = hero, id = 6 name = godman, id = 99 name = srk]
}
}
This is how we sort user defined object array using static overloaded method java.util.Arrays.sort(Object[] arr)
Now, how can we sort the Employee[] by name field or other field like email(Assume this field exists)?
We can make use of java.util.Arrays.sort(Object[] arr, Comparator<? Super T> c)
There are multiple ways to implement a comparator, let’s look at few approaches.
Approach 1: Update Employee class that will implement Comparable and Comparator
class Employee implements Comparable<Employee>, Comparator<Employee> {
private int id;
private String name;
public Employee() {}
public Employee(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public int compareTo(Employee employee) {
return this.id - employee.id;
/*-
* Note:
* For ascending order/Natural order: return this.id - employee.id;
* For descending order/Reverse order: return employee.id - this.id;
*
* returns 0 - when this object's id is equal to specified object
* returns -1 - when this object's id is less than specified object
* returns 1 - when this object's id is greater than specified object
*/
}
@Override
public int compare(Employee e1, Employee e2) {
return e1.getName().compareTo(e2.getName());
}
@Override
public String toString() {
return "id = " + id + " name = " + name;
}
public int getId() {
return id;
}
public String getName() {
return name;
}
}
class Demo {
public static void main(String[] args) {
Employee[] employees = new Employee[3];
employees[0] = new Employee(99, "srk");
employees[1] = new Employee(2, "hero");
employees[2] = new Employee(6, "godman");
System.out.println("Employee[] before sorting = " + Arrays.toString(employees));
java.util.Arrays.sort(employees);
System.out.println(
"Employee[] with natural ordering through Comparable = " + Arrays.toString(employees));
java.util.Arrays.sort(employees, new Employee());// passing Comparator impl as 2nd argument
System.out.println(
"Employee[] with custom sorting by name through Comparator = "
+ Arrays.toString(employees));
}
}
Output:
Employee[] before sorting = [id = 99 name = srk, id = 2 name = hero, id = 6 name = godman]
Employee[] with natural ordering through Comparable = [id = 2 name = hero, id = 6 name = godman, id = 99 name = srk]
Employee[] with custom sorting by name through Comparator = [id = 6 name = godman, id = 2 name = hero, id = 99 name = srk]
Approach 2: Expose a static utility method from Employee class that returns a Comparator
class Employee implements Comparable<Employee> {
private int id;
private String name;
public Employee(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public int compareTo(Employee employee) {
return this.id - employee.id;
/*-
* Note:
* For ascending order/Natural order: return this.id - employee.id;
* For descending order/Reverse order: return employee.id - this.id;
*
* returns 0 - when this object's id is equal to specified object
* returns -1 - when this object's id is less than specified object
* returns 1 - when this object's id is greater than specified object
*/
}
@Override
public String toString() {
return "id = " + id + " name = " + name;
}
public int getId() {
return id;
}
public String getName() {
return name;
}
public static Comparator<Employee> getEmployeeComparator() {
return new Comparator<Employee>() {
@Override
public int compare(Employee o1, Employee o2) {
return o1.getName()
.compareTo(o2.getName()); // java.lang.String implements Comparable<String>
/*-
* Note:
* For ascending order/natural order: o1.getName().compareTo(o2.getName())
* For descending order/reverse order: o2.getName().compareTo(o1.getName())
*
*/
}
};
}
}
class Demo {
public static void main(String[] args) {
Employee[] employees = new Employee[3];
employees[0] = new Employee(99, "srk");
employees[1] = new Employee(2, "hero");
employees[2] = new Employee(6, "godman");
System.out.println("Employee[] before sorting = " + Arrays.toString(employees));
java.util.Arrays.sort(employees);
System.out.println(
"Employee[] with natural ordering through Comparable = " + Arrays.toString(employees));
java.util.Arrays.sort(employees, Employee.getEmployeeComparator());
System.out.println(
"Employee[] with custom sorting by name through Comparator = "
+ Arrays.toString(employees));
}
}
Output:
Employee[] before sorting = [id = 99 name = srk, id = 2 name = hero, id = 6 name = godman]
Employee[] with natural ordering through Comparable = [id = 2 name = hero, id = 6 name = godman, id = 99 name = srk]
Employee[] with custom sorting by name through Comparator = [id = 6 name = godman, id = 2 name = hero, id = 99 name = srk]
Approach 3: Externalize the Comparator from the Employee class
Assume Employee is a part of a third-party library, where in you have no control to update Employee class with custom comparators as mentioned above two approaches.
In such scenarios we have to define a custom comparator outside the class, as shown below.
class Employee implements Comparable<Employee> {
private int id;
private String name;
public Employee(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public int compareTo(Employee employee) {
return this.id - employee.id;
/*-
* Note:
* For ascending order/Natural order: return this.id - employee.id;
* For descending order/Reverse order: return employee.id - this.id;
*
* returns 0 - when this object's id is equal to specified object
* returns -1 - when this object's id is less than specified object
* returns 1 - when this object's id is greater than specified object
*/
}
@Override
public String toString() {
return "id = " + id + " name = " + name;
}
public int getId() {
return id;
}
public String getName() {
return name;
}
}
class Demo {
public static void main(String[] args) {
Employee[] employees = new Employee[3];
employees[0] = new Employee(99, "srk");
employees[1] = new Employee(2, "hero");
employees[2] = new Employee(6, "godman");
System.out.println("Employee[] before sorting = " + Arrays.toString(employees));
java.util.Arrays.sort(employees);
System.out.println(
"Employee[] with natural ordering through Comparable = " + Arrays.toString(employees));
Comparator<Employee> employeeComparator =
new Comparator<Employee>() {
@Override
public int compare(Employee e1, Employee e2) {
return e1.getName().compareTo(e2.getName());
}
};
java.util.Arrays.sort(employees, employeeComparator);
System.out.println(
"Employee[] with custom sorting by name through Comparator = "
+ Arrays.toString(employees));
}
}
Output:
Employee[] before sorting = [id = 99 name = srk, id = 2 name = hero, id = 6 name = godman]
Employee[] with natural ordering through Comparable = [id = 2 name = hero, id = 6 name = godman, id = 99 name = srk]
Employee[] with custom sorting by name through Comparator = [id = 6 name = godman, id = 2 name = hero, id = 99 name = srk]
Using Lambda Expression
Starting Java8, we can use lambda expression to define a custom comparator.
Comparator<Employee> sortByName = (e1, e1) -> e1.getName().compareTo(e2.getName());
class Employee implements Comparable<Employee> {
private int id;
private String name;
public Employee(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public int compareTo(Employee employee) {
return this.id - employee.id;
/*-
* Note:
* For ascending order/Natural order: return this.id - employee.id;
* For descending order/Reverse order: return employee.id - this.id;
*
* returns 0 - when this object's id is equal to specified object
* returns -1 - when this object's id is less than specified object
* returns 1 - when this object's id is greater than specified object
*/
}
@Override
public String toString() {
return "id = " + id + " name = " + name;
}
public int getId() {
return id;
}
public String getName() {
return name;
}
}
class Demo {
public static void main(String[] args) {
Employee[] employees = new Employee[3];
employees[0] = new Employee(99, "srk");
employees[1] = new Employee(2, "hero");
employees[2] = new Employee(6, "godman");
System.out.println("Employee[] before sorting = " + Arrays.toString(employees));
java.util.Arrays.sort(employees);
System.out.println(
"Employee[] with natural ordering through Comparable = " + Arrays.toString(employees));
Comparator<Employee> sortByName =
(e1, e2) -> e1.getName().compareTo(e2.getName());
java.util.Arrays.sort(employees, sortByName);
/*-
* Or you can pass comparator directly to sort inline
* java.util.Arrays.sort(employees, (e1, e2) -> e1.getName().compareTo(e2.getName()));
* -----------------
*
*/
System.out.println(
"Employee[] with custom sorting by name through Comparator = "
+ Arrays.toString(employees));
}
}
Output:
Employee[] before sorting = [id = 99 name = srk, id = 2 name = hero, id = 6 name = godman]
Employee[] with natural ordering through Comparable = [id = 2 name = hero, id = 6 name = godman, id = 99 name = srk]
Employee[] with custom sorting by name through Comparator = [id = 6 name = godman, id = 2 name = hero, id = 99 name = srk]
java.util.Comparator<T> interface’s 9 static methods and their usage
Here is the list of static method defined in java.util.Comparator<T> interface
Refer: https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html
1. comparing(Function<? super T, ? extends U> keyExtractor) Usage
Implementation from java.util.Comparator<T> interface
public static <T, U extends Comparable<? super U>> Comparator<T> comparing(
Function<? super T, ? extends U> keyExtractor) {
Objects.requireNonNull(keyExtractor);
return (Comparator<T> & Serializable)
(c1, c2) -> keyExtractor.apply(c1).compareTo(keyExtractor.apply(c2));
}
Example: Below code demonstrates the usage of Comparator.comparing and sort employee by name
Using java.util.Function<T,R> and passing function
java.util.function.Function<Employee, String> keyExtractor = emp -> emp.getName();
java.util.Arrays.sort(employees, java.util.Comparator.comparing(keyExtractor));
java.util.Arrays.sort(employees, sortByname);
Using lambda expression and passing lambda
java.util.Arrays.sort(employees, Comparator.comparing(emp -> emp.getName()));
Using Method reference
java.util.Arrays.sort(employees, Comparator.comparing(Employee::getName))
2. comparing(Function<? super T, ? extends U> keyExtractor, Comparator<? super U> keyComparator) Usage
Implementation from java.util.Comparator<T> interface
public static <T, U> Comparator<T> comparing(
Function<? super T, ? extends U> keyExtractor,
Comparator<? super U> keyComparator) {
Objects.requireNonNull(keyExtractor);
Objects.requireNonNull(keyComparator);
return (Comparator<T> & Serializable)
(c1, c2) -> keyComparator.compare(keyExtractor.apply(c1),
keyExtractor.apply(c2));
}
Example: Below code demonstrates the usage of Comparator.comparing and sort employee by name
If we want to sort by employee name in reverse
java.util.function.Function<Employee, String> keyExtractor = emp -> emp.getName();
java.util.Comparator<String> keyComparator = (s1, s2) -> s2.compareTo(s1); // sorts employee names in reverse order
java.util.Comparator<Employee> sortByNameInReverse =
java.util.Comparator.comparing(keyExtractor, keyComparator);
java.util.Arrays.sort(employees, sortByNameInReverse);
Output:
Employee[] before sorting = [id = 99 name = srk, id = 2 name = hero, id = 6 name = godman]
Employee[] with natural ordering through Comparable = [id = 2 name = hero, id = 6 name = godman, id = 99 name = srk]
Employee[] with custom sorting by name through Comparator = [id = 99 name = srk, id = 2 name = hero, id = 6 name = godman]
3. reverseOrder() Usage
Implementation from java.util.Comparator<T> interface
public static <T extends Comparable<? super T>> Comparator<T> reverseOrder() {
return Collections.reverseOrder();
}
Alternatively to achieve the same result you can use java.util.Comparator.reverseOrder()
java.util.function.Function<Employee, String> keyExtractor = emp -> emp.getName();
java.util.Comparator<Employee> sortByNameInReverse =
java.util.Comparator.comparing(keyExtractor, Comparator.reverseOrder());
java.util.Arrays.sort(employees, sortByNameInReverse);
Or we can use java.util.Collections.reverseOrder()
java.util.function.Function<Employee, String> keyExtractor = emp -> emp.getName();
java.util.Comparator<Employee> sortByNameInReverse =
java.util.Comparator.comparing(keyExtractor, java.util.Collections.reverseOrder());
java.util.Arrays.sort(employees, sortByNameInReverse);
4. naturalOrder() Usage
Implementation from java.util.Comparator<T> interface
@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> Comparator<T> naturalOrder() {
return (Comparator<T>) Comparators.NaturalOrderComparator.INSTANCE;
}
The java.util.List<T> interface has a default method sort(Comparator<T> comparator)
Example usage
List<Integer> ints = Arrays.asList(99, 4, 6); // Returns a read only collection, throws java.lang.UnSupportedOperationException when you try to add element to the list even outside a for loop
Starting Java9 you can use the following get an immutable list
List<Integer> ints = List.of(99,4,6);
Now to sort the list we can use
Collection.sort(ints); // throws java.lang.UnSupportedOperationException when list is initialized with List.of(99,4,6), but works when list is initialized with Arrays.asList(99,4,6);
ints.sort(Comparator.naturalOrder()); // throws java.lang.UnSupportedOperationException when list is initialized with List.of(99,4,6), but works when list is initialized with Arrays.asList(99,4,6);
Output:
[4,6,99]
5. reverseOrder() Usage
Implementation from java.util.Comparator<T> interface
public static <T extends Comparable<? super T>> Comparator<T> reverseOrder() {
return Collections.reverseOrder();
}
Same example as above, but the only change is
ints.sort(Comparator.reverseOrder())
Output:
[99,6,4]
5. nullsFirst(Comparator<? super T> comparator) Usage
Implementation from java.util.Comparator<T> interface
public static <T> Comparator<T> nullsFirst(Comparator<? super T> comparator) {
return new Comparators.NullComparator<>(true, comparator);
}
Here is what javadoc says
Returns a null-friendly comparator that considers null to be less than non-null. When both are null, they are considered equal.
Example1:
List<String> fruits = Arrays.asList("banana", "grape", null, "apple");
fruits.sort(Comparator.nullsFirst(Comparator.naturalOrder()));
System.out.println("fruits = " + fruits); // Prints [null, apple, banana, grape]
Example2:
List<String> fruits = Arrays.asList("banana", "grape", null, "apple");
fruits.sort(Comparator.nullsFirst(Comparator.reverseOrder()));
System.out.println("fruits = " + fruits); // Prints [null, grape, banana, apple]
6. nullsLast(Comparator<? super T> comparator) Usage
Implementation from java.util.Comparator<T> interface
public static <T> Comparator<T> nullsLast(Comparator<? super T> comparator) {
return new Comparators.NullComparator<>(false, comparator);
}
Here is what javadoc says
Returns a null-friendly comparator that considers null to be greater than non-null. When both are null, they are considered equal
Example1:
List<String> fruits = Arrays.asList("banana", "grape", null, "apple");
fruits.sort(Comparator.nullsLast(Comparator.naturalOrder()));
System.out.println("fruits = " + fruits); // Prints [apple, banana, grape, null]
Example2:
List<String> fruits = Arrays.asList("banana", "grape", null, "apple");
fruits.sort(Comparator.nullsLast(Comparator.reverseOrder()));
System.out.println("fruits = " + fruits); // Prints [grape, banana, apple, null]
7. comparingInt(ToIntFunction<? super T> keyExtractor) Usage
Takes only int value as sort key, unlike comparing method which takes any type as sort key
Implementation from java.util.Comparator<T> interface
public static <T> Comparator<T> comparingInt(ToIntFunction<? super T> keyExtractor) {
Objects.requireNonNull(keyExtractor);
return (Comparator<T> & Serializable)
(c1, c2) -> Integer.compare(keyExtractor.applyAsInt(c1), keyExtractor.applyAsInt(c2));
}
comparingInt() is a specialized form of comparing(), which allows us to specify a function that extracts a Comparable key from each object. The comparingInt() method is more efficient than comparing() when comparing integer keys because it avoids the overhead of boxing and unboxing
8. comparingLong(ToLongFunction<? super T> keyExtractor) Usage
Takes only long value as sort key, unlike comparing method which takes any type as sort key
Implementation from java.util.Comparator<T> interface
public static <T> Comparator<T> comparingLong(ToLongFunction<? super T> keyExtractor) {
Objects.requireNonNull(keyExtractor);
return (Comparator<T> & Serializable)
(c1, c2) -> Long.compare(keyExtractor.applyAsLong(c1), keyExtractor.applyAsLong(c2));
}
9. comparingDouble(ToDoubleFunction<? super T> keyExtractor) Usage </>
Takes only double value as sort key, unlike comparing method which takes any type as sort key
Implementation from java.util.Comparator<T> interface
public static<T> Comparator<T> comparingDouble(ToDoubleFunction<? super T> keyExtractor) {
Objects.requireNonNull(keyExtractor);
return (Comparator<T> & Serializable)
(c1, c2) -> Double.compare(keyExtractor.applyAsDouble(c1), keyExtractor.applyAsDouble(c2));
}
Example for 7,8,9 combined:
class Person {
private int age;
private long id;
private double weight;
public Person(int age, long id, double weight) {
this.age = age;
this.id = id;
this.weight = weight;
}
public int getAge() {
return age;
}
public long getId() {
return id;
}
public double getWeight() {
return weight;
}
}
class Sorting {
public static void main(String[] args) {
Person[] persons = new Person[3];
persons[0] = new Person(23, 106, 70.5);
persons[1] = new Person(33, 10936216, 69.9);
persons[2] = new Person(49, 1, 70.0);
// Sort persons by age int type
java.util.Arrays.sort(persons, java.util.Comparator.comparingInt(Person::getAge));
Arrays.asList(persons).forEach(pers -> System.out.println(pers.getAge()));
// Sort employees by empId long type
java.util.Arrays.sort(persons, java.util.Comparator.comparingLong(Person::getId));
Arrays.asList(persons).forEach(pers -> System.out.println(pers.getId()));
// Sort employees by weight double type
java.util.Arrays.sort(persons, java.util.Comparator.comparingDouble(Person::getWeight));
Arrays.asList(persons).forEach(pers -> System.out.println(pers.getWeight()));
}
}
Given the following employees
Employee[] employees = new Employee[3];
employees[0] = new Employee(99, "srk");
employees[1] = new Employee(2, "SRK");
employees[2] = new Employee(6, "godman");
Sorting employee by names will result in {"SRK", godman, "srk"}
Applying the keyComparator String.CASE_INSENSITIVE_ORDER you’ll get {"godman", "SRK", "srk"}
java.util.function.Function<Employee, String> keyExtractor = emp -> emp.getName();
java.util.Comparator<Employee> sortByName = Comparator.comparing(keyExtractor, String.CASE_INSENSITIVE_ORDER);
java.util.Arrays.sort(employees, sortByName);
java.util.Comparator<T> interface’s 7 default methods and their usage
1. thenComparing(Comparator<? super T> other) Usage
You can think of thenComparing like SQL’s ORDER BY clause with one or more columns
List<Person> persons = new ArrayList<>();
// add persons to the list
Comparator<Person> byName = Comparator.comparing(Person::getName);
Comparator<Person> byAge = Comparator.comparingInt(Person::getAge).reversed();
Comparator<Person> byId = Comparator.comparingInt(Person::getId);
persons.sort(byName.thenComparing(byAge).thenComparing(byId));
2. thenComparing(Function<? Super T, ? extends U> keyExtractor) Usage
SQL Example: SELECT * FROM employees ORDER BY department, salary;
Java Example:
List<Employee> employees = getEmployees();
Comparator<Employee> comparator = Comparator
.comparing(Employee::getDepartment)
.thenComparing(Employee::getSalary);
3. thenComparing(Function<? super T,? extends U> keyExtractor, Comparator<? super U> keyComparator) Usage
Example:
Comparator<Person> byAge = Comparator.comparing(Person::getAge);
Comparator<Person> bySalary = Comparator.comparing(Person::getSalary);
Comparator<Person> byName = Comparator.comparing(Person::getName);
// sort by age, then by salary, then by name
List<Person> sortedPeople = people.stream()
.sorted(byAge.thenComparing(bySalary, Comparator.reverseOrder())
.thenComparing(byName))
.collect(Collectors.toList());
4. reversed() Usage
SQL query example: SELECT * FROM employees ORDER BY age DESC;
Java Example:
Comparator<Employee> byAge = Comparator.comparing(Employee::getAge);
List<Employee> sortedEmployees = employees.stream().sorted(byAge.reversed()).collect(Collectors.toList());
5. thenComparingInt(ToIntFunction<? super T> keyExtractor)) Usage
Returns a lexicographic-order comparator with a function that extracts an int sort key.
6. thenComparingLong(ToLongFunction<? super T> keyExtractor) Usage
Returns a lexicographic-order comparator with a function that extracts a long sort key.
7. thenComparingDouble(ToDoubleFunction<? super T> keyExtractor) Usage
Returns a lexicographic-order comparator with a function that extracts a double sort key.
Example for 5,6,7 combined:
class Employee {
private String name;
private String department;
private int age;
private long id;
private double weight;
public Employee(String name, String department, int age, long id, double weight) {
this.name = name;
this.department = department;
this.age = age;
this.id = id;
this.weight = weight;
}
public String getName() {
return name;
}
public String getDepartment() {
return department;
}
public int getAge() {
return age;
}
public long getId() {
return id;
}
public double getWeight() {
return weight;
}
@Override
public String toString() {
return "["
+ "department = "
+ department
+ " name = "
+ name
+ " age = "
+ age
+ " id = "
+ id
+ " weight = "
+ weight
+ "]";
}
}
class Demo {
public static void main(String[] args) {
Employee[] employees = new Employee[3];
employees[0] = new Employee("srk", "IT", 33, 106, 70.5);
employees[1] = new Employee("hero", "Sales", 33, 10936216, 69.9);
employees[2] = new Employee("srk", "IT", 49, 1, 70.0);
// Sort by department(String), name(String), then sort by age(int)
System.out.println("=== Sort by department, name, age ===");
java.util.Arrays.sort(
employees,
java.util.Comparator.comparing(Employee::getDepartment)
.thenComparing(Employee::getName)
.thenComparingInt(Employee::getAge));
for (Employee employee : employees) {
System.out.println(employee);
}
// Sort by department(String), name(String), then sort by age(int), then sort by id(long)
System.out.println("=== Sort by department, name, age, id ===");
java.util.Arrays.sort(
employees,
java.util.Comparator.comparing(Employee::getDepartment)
.thenComparing(Employee::getName)
.thenComparingInt(Employee::getAge)
.thenComparingLong(Employee::getId));
for (Employee employee : employees) {
System.out.println(employee);
}
// Sort by department(String), name(String), then sort by age(int), then sort by id(long), then sort by weight(double)
System.out.println("=== Sort by name, age, id, weight ===");
java.util.Arrays.sort(
employees,
java.util.Comparator.comparing(Employee::getDepartment)
.thenComparing(Employee::getName)
.thenComparingInt(Employee::getAge)
.thenComparingLong(Employee::getId)
.thenComparingDouble(Employee::getWeight));
for (Employee employee : employees) {
System.out.println(employee);
}
}
}
Sorting collections using Collection.sort()
java.util.Collection static utility class has 2 sort overloaded methods
static <T extends Comparable<? super T>> sort(List<T> list)Sorts the specified list into ascending order, according to the natural ordering of its elements.
static <T> void sort(List<T> list, Comparator<? super T> c)Sorts the specified list according to the order induced by the specified comparator.
static <T> Comparator<T> reverseOrder()Returns a comparator that imposes the reverse of the natural ordering on a collection of objects that implement the Comparable interface.
static <T> Comparator<T> reverseOrder(Comparator<T> cmp)Returns a comparator that imposes the reverse ordering of the specified comparator.
class Employee implements Comparable<Employee> {
private int id;
private String name;
private double sal;
public Employee(int id, String name, double sal) {
this.id = id;
this.name = name;
this.sal = sal;
}
public int getId() {
return id;
}
public String getName() {
return name;
}
public double getSal() {
return sal;
}
@Override
public String toString() {
return "Employee={id=" + id + ",name=" + name + ",sal=" + sal + "}";
}
public int compareTo(Employee o) {
return this.id - o.id; // Sorts employee by id in ascending order
}
}
class Demo {
public static void main(String[] args) {
List<Employee> employees =
Arrays.asList(
new Employee(3, "jhonnie", 100.1),
new Employee(2, "dhoela", 500.9),
new Employee(1, "grey", 8889.1));
// Print employees
System.out.println("Employees = " + employees);
// Collections.sort(employees);
/*
Above Line doesn't compile when Employee class doesn't implement Comparable interface at least to do sort by natural order.
It's a prerequisite to implement Comparable or Comparator for an collection that's passed to Collections.sort()
*/
// Sort employees by id in natural order
Collections.sort(employees);
System.out.println("Sort employees by id= " + employees);
// Sort employees by id in reverse order
Collections.sort(employees, Collections.reverseOrder());
System.out.println("Sort employees by id in reverse order= " + employees);
// Sort employees by id and then name
Collections.sort(employees, (emp1, emp2) -> emp1.getName().compareTo(emp2.getName()));
System.out.println("Sort employees by id and then name=" + employees);
// Sort employees by id and then sort by length of the name in natural/ascending order
Collections.sort(employees, (emp1, emp2) -> emp1.getName().length() - emp2.getName().length());
System.out.println("Sort employees by id, sort by name in ascending order=" + employees);
// Sort employes by id and then sort by length of the name in descending order
Collections.sort(
employees,
Collections.reverseOrder(
(emp1, emp2) -> emp2.getName().length() - emp1.getName().length()));
System.out.println("Sort employees by id, sort by name in descending order=" + employees);
}
}
java.util.List default method void sort(Comparator<? super String> c)
Example: Sorting a list of strings using java.util.List’s default sort() method.
private static void sort_a_list_of_strings_with_list_dot_sort_method() {
List<String> fruits = Arrays.asList("banana", "apple", "tomato");
fruits.sort( // introduced in Java 1.8 - as default method that takes comparator argument
Comparator
.naturalOrder()); // Expects the object in collection to implement at least Comparable
// or Comparator Interface
System.out.println("Sort Fruits in natural order=" + fruits);
fruits.sort(Comparator.reverseOrder());
System.out.println("Sort Fruits in reverse order=" + fruits);
}
java.util.stream.Stream interface has Stream sorted(); abstract method
Example1: stream.sorted() demo
private static void filter_strings_with_length_lteq_5_and_sort_using_streams() {
List<String> strings = Arrays.asList("asasdfasfs", "apple", "banana", "grape", "abc");
List<String> filteredAndSortedList =
strings.stream().filter(str -> str.length() <= 5).sorted().collect(Collectors.toList());
System.out.println("Filtered and sorted list = " + filteredAndSortedList); // prints: [abc, apple, grape]
}
Example2: stream.sorted(Comparator<> comparator) overloaded method demo
private static void filter_strings_with_length_gteq_5_and_sort_by_str_last_char_using_streams() {
List<String> strings = Arrays.asList("asasdfasfs", "apple", "banana", "grape", "abc");
List<String> filteredAndSortedList =
strings.stream()
.filter(str -> str.length() >= 5)
.sorted(
(str1, str2) ->
Character.compare(
str1.charAt(str1.length() - 1), str2.charAt(str2.length() - 1)))
.collect(Collectors.toList());
System.out.println(
"Filter strs with len(<=5) and sort by last char of each string = "
+ filteredAndSortedList); // prints: [banana, apple, grape, asasdfasfs]
}
Usage of toMap() overloaded methods from java.util.stream.Collectors utility class
Overloaded toMap() variant 1
Collector<T, ?, Map<K,U>> toMap(Function<? super T, ? extends K> keyMapper,
Function<? super T, ? extends U> valueMapper) {
/* IMPL code */
}
Here is the excerpt from the javadoc
Parameters:
keyMapper - a mapping function to produce keys
valueMapper - a mapping function to produce values
Applicability: Use this overloaded toMap() method when you want to transform a collection to Map provided the collection that you are streaming over has no duplicate keys, and you are not expecting the resultant map to be sorted.
Example: Given a Set
Set<String> fruits = new HashSet<>(Arrays.asList("apple", "banana", "grape"));
Map<String, Integer> strAndLengths =
fruits.stream().collect(Collectors.toMap(str -> str, str -> str.length()));
strAndLengths.entrySet().stream().forEach(System.out::println);
// Prints apple=5 banana=6 grape=5 in separate lines on console
System.out.println(strAndLengths);// prints {apple=5, banana=6, grape=5}
Overloaded toMap() variant 2
Collector<T, ?, Map<K,U>> toMap(Function<? super T, ? extends K> keyMapper,
Function<? super T, ? extends U> valueMapper,
BinaryOperator<U> mergeFunction) {
return toMap(keyMapper, valueMapper, mergeFunction, HashMap::new);
}
javadoc for toMap() with merge function in case of key collisions
Here is the excerpt from the javadoc
Parameters:
keyMapper a mapping function to produce keys
valueMapper a mapping function to produce values
mergeFunction a merge function, used to resolve collisions between values associated with the same key, as supplied to Map.merge(Object, Object, BiFunction)
Applicability: Use this toMap() overloaded method when you think there could be a chance of key collisions, like when you are streaming over a collection like List<String>, List<Integer>, List<Employee> except map(because map doesn’t have duplicate keys).
Example: Given an int[] convert to Map with frequency of ints, input: {1,3,2,3} output: {1=1, 2=1, 3=2}
int[] ints = {1, 3, 2, 3};
java.util.Map<Integer, Integer> intFrequency =
java.util.Arrays.stream(ints) // Returns IntStream
.boxed() // Returns Stream<Integer>
.collect(
java.util.stream.Collectors.toMap(
elm -> elm, elm -> 1, (val1, val2) -> val1 + val2));
intFrequency.entrySet().stream().forEach(System.out::println);
// prints 1=1 2=1 3=2 in separate line
System.out.println(intFrequency); // Prints {1=1, 2=1, 3=2}
Overloaded toMap() variant 3
Collector<T, ?, M> toMap(Function<? super T, ? extends K> keyMapper,
Function<? super T, ? extends U> valueMapper,
BinaryOperator<U> mergeFunction, Supplier<M> mapFactory) {
// IMPL CODE
}
Here is the excerpt from the javadoc
keyMapper - a mapping function to produce keys
valueMapper - a mapping function to produce values
mergeFunction - a merge function, used to resolve collisions between values associated with the same key, as supplied to Map.merge(Object, Object, BiFunction)
mapSupplier - a function which returns a new, empty Map into which the results will be inserted
Applicability: Use this overloaded toMap() variant when you want to sort the upstream Map by keys or values and preserve the sort order.
Example: Given an int[] arr get the arr frequency and sort by key and values
int[] input = {1, 4, 3, 4, 5, 3, 1, 7, 5, 4, 7, 4};
// Sort by keys
Map<Integer, Integer> inputSortedByKey =
Arrays.stream(input)
.boxed()
.collect(Collectors.toMap(elm -> elm, elm -> 1, (val1, val2) -> val1 + val2))
/* Instead of Collectors.toMap we can use
.collect(Collectors.groupingBy(elm -> elm, Collectors.counting()))
but that would returns Map<Integer, Long> as Collectors.counting() returns long
*/
.entrySet()
.stream()
.sorted(
Map.Entry.comparingByKey()) // to sort by values use: Map.Entry.comparingByValue()
.collect(
Collectors.toMap(
Map.Entry::getKey,
Map.Entry::getValue,
(val1, val2) ->
val1, // No key collisions at this point but still have to pass this func
// to honour the Collectors.toMap method signature
LinkedHashMap::new));
System.out.println(inputSortedByKey); // Prints: {1=2, 3=2, 4=4, 5=2, 7=2}
In summary, these are some use cases covered in this post
java.util.Arraysstatic utility class .sort() method - To sort primitives, wrappers, user-defined objectsjava.util.Collectionsstatic utility class .sort() method - To sort wrappers, user-defined objects, that can also takes a custom comparatorjava.util.stream.Streaminterface abstract sorted() method - To sort wrappers, user-defined objects that can also take a custom comparator.java.util.Listinterface default sort() method - that takes a custom comparator
Also, covered java.util.Comparator interface’s default methods like thenComparing() to chain multiple comparators. And, covered some related topics like sorting a map by key, values, in the process superficially touched java.util.stream.Collectors static utility class’s methods like toMap() and explained how to preserve the sort order when returning a map after streaming over a map collection. And explained merge function purpose and applicability in toMap().