Sorting an ArrayList in java

If the data in your ArrayList has a natural sorting order (ie, implements Comparable, as do String, Integer, ...), you can simply call the static Collections.sort() method. This is a stable, guaranteed n log n sort.

Collections.sort(yourArrayList);

If you want to choose a different sort criterion or your data doesn't implement xxxx, you will have to define a Comparator and pass that to the sort() method.

Collections.sort(yourArrayList, yourComparator);

Check out Collections for other useful utility methods.

Sorting an array in java

For sorting Arrays.sort(arr) is used, which is static function in arrays class.

Here a is array and method uses a tuned version of the QuickSort algorithm

int arr[] = {4,3,1};
Arrays.sort(arr);

This will sort the array in ascending order.

Seeing various sorting methods:

 

Method Arrays sort methods	Description
Arrays.sort(pa);	Sorts the elements of the array of a primitive type into ascending order using their natural ordering.
Arrays.sort(pa, from, to);	Sorts the elements pa[from]...pa[to-1] of a primitive type. into ascending order.
Arrays.sort(oa);	Sorts the elements of the array of an object type into ascending order, using the order defined by Comparable interface, which defines the compareTo method. Note that many Java classes such as String (but not StringBuffer), Double, BigInteger, etc implement Comparable.
Arrays.sort(oa, from, to);	Sorts the elements of the array, in the range from...to of an object type into ascending order.
Arrays.sort(oa, comp);	Sorts the elements of the array of an object type into ascending order, using the Comparator comp.
Arrays.sort(oa, from, to, comp);	Sorts the elements of the array, in the range from...to of an object type into ascending order using the Comparator comp.

Implementing compareTo() : Sorting in natural ordering using compareTo()

Defining the criteria for sorting

Suppose we have list of Employees. We have to sort them. By default, you can't sort it, until you define some criteria. Say you define sorting as first name of employee, or you may say sort on the basis of employee id or their salary. So first thing is we have to define some criteria for sorting. This defines "natural ordering" on which sort can be done.

How to define "natural order" in java?

For this, we have to implement Comparable interface, which has compareTo method, which decides how we put natural ordering on the object.

Example:

Employee’s natural ordering would be done according to the employee id. For that, above Employee class must be altered to add the comparing ability as follows.

public class Employee implements Comparable<Employee> {
    private int empId;
    private String name;
    private int age;
    
    /**
     * Compare a given Employee with this object.
     * If employee id of this object is 
     * greater than the received object,
     * then this object is greater than the other.
     */
    public int compareTo(Employee o) {
        return this.empId - o.empId ;
    }
    ….
}

So this compareTo() method does the trick of implementing natural ordering. So if we have 2 Employees, emp1.id – emp2.id is negative, then emp1 falls before emp2 in this ordering. We can say it like this:

emp1.id < emp2.id – emp1 falls before emp2 in natural ordering

emp1.id == emp2.id – emp1 falls with emp2 in natural ordering

emp1.id > emp2.id – emp1 falls after emp2 in natural ordering

 

Sorting the employee list:

 

We’ll write a class to test this natural ordering mechanism. Following class use the Collections.sort(List) method to sort the given list in natural order.

import java.util.*;

public class TestEmployeeSort {
    
    public static void main(String[] args) {     
        List coll = Util.getEmployees();
        Collections.sort(coll); // sort method
        printList(coll);
    }
    
    private static void printList(List<Employee> list) {
        System.out.println("EmpId\tName\tAge");
        for (Employee e: list) {
            System.out.println(e.getEmpId() + "\t" + e.getName() + "\t" + e.getAge());
        }
    }
}

Similarly to sort on the basis of name : write compareTo like this:

public int compareTo(Employee other) {
    return name.compareTo(o2.getName());
//here compareTo() method of String is called
}

Collections.sort() vs Arrays.sort()

Difference between the Collections.sort() and Arrays.sort()?

Difference between the two is input. Collections.sort() has a input as List so it does a translation of List to array and vice versa which is an additional step while sorting. So this should be used when you are trying to sort a list. Arrays.sort is for arrays so the sorting is done directly on the array. So clearly it should be used when you have a array available with you and you want to sort it.

Algorithm – Algorithm seems to be same.

Locale-based or Natural Language based text comparison in java

The String class doesn't have the ability to compare text from a natural language perspective.

Its equals and compareTo methods compare the individual char values in the string. If the char value at index n in name1 is the same as the char value at index n in name2 for all n in both strings, the equals method returns true.

The java.text.Collator class provides natural language comparisons. Natural language comparisons depend upon locale-specific rules that determine the equality and ordering of characters in a particular writing system.A Collator object understands that people expect "cat" to come before "Hat" in a dictionary. Using a collator comparison, the following code prints cat < Hat.

Collator collator = Collator.getInstance(new Locale("en", "US")); 

//OR             Collator.getInstance(Locale.US);

int comparison = collator.compare("cat", "Hat");
if (comparison < 0) {
  System.out.printf("%s < %s\n", "cat", "Hat");
} else {
  System.out.printf("%s < %s\n", "Hat", "cat" );
}

So this can be used for sorting of words based on locale, eg using Collections.sort() :

List<String> boyNames= new ArrayList<String>();
boyNames.add("Ankit");
boyNames.add("Himanshu");
boyNames.add("Rohit");
boyNames.add("Neerav");
boyNames.add("Gaurav");

//
// Define a collator for US English.
//
Collator collator = Collator.getInstance(Locale.US);
//
// Sort the list base on the collator
//
Collections.sort(boyNames, collator);

References:

• Collator