Java tutorials > Core Java Fundamentals > Data Structures and Collections > How to sort a Collection?

How to sort a Collection?

This tutorial explains how to sort a Collection in Java, covering various methods and considerations. We'll delve into using `Collections.sort()`, implementing the `Comparable` interface, and utilizing `Comparator` for custom sorting.

Using Collections.sort() for List Sorting

The `Collections.sort()` method sorts a List in ascending order. This method modifies the original list directly. It's applicable to Lists containing elements that implement the `Comparable` interface, such as String, Integer, etc. In this example, we sort a list of Strings lexicographically. The output shows the list before and after sorting.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SortList {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>();
        names.add("Charlie");
        names.add("Alice");
        names.add("Bob");

        System.out.println("Before sorting: " + names);
        Collections.sort(names);
        System.out.println("After sorting: " + names);
    }
}

Sorting with Comparable Interface

When you need to sort objects of a custom class, you can implement the `Comparable` interface. This interface defines a `compareTo()` method, which determines the natural ordering of the objects. In the example, the `Student` class implements `Comparable`, and the `compareTo()` method compares students based on their names. This dictates how the `Collections.sort()` method will sort the list of students.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Student implements Comparable<Student> {
    private String name;
    private int age;

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

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    @Override
    public int compareTo(Student other) {
        return this.name.compareTo(other.name); // Sort by name
    }

    @Override
    public String toString() {
        return "Student{name='" + name + "', age=" + age + "}"; 
    }

    public static void main(String[] args) {
        List<Student> students = new ArrayList<>();
        students.add(new Student("Charlie", 20));
        students.add(new Student("Alice", 22));
        students.add(new Student("Bob", 21));

        System.out.println("Before sorting: " + students);
        Collections.sort(students);
        System.out.println("After sorting: " + students);
    }
}

Sorting with Comparator Interface (Custom Sorting)

The `Comparator` interface allows you to define custom sorting logic without modifying the class itself. This is particularly useful when you need to sort objects based on different criteria or when you don't have control over the class definition. In the example, an anonymous `Comparator` is created to sort students by age. A lambda expression provides a more concise way to achieve the same result, as shown for sorting by name. `Comparator` provides flexibility to control exactly how the comparison is performed.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Student {
    private String name;
    private int age;

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

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    @Override
    public String toString() {
        return "Student{name='" + name + "', age=" + age + "}";
    }
}

public class SortByAge {
    public static void main(String[] args) {
        List<Student> students = new ArrayList<>();
        students.add(new Student("Charlie", 20));
        students.add(new Student("Alice", 22));
        students.add(new Student("Bob", 21));

        System.out.println("Before sorting: " + students);

        Collections.sort(students, new Comparator<Student>() {
            @Override
            public int compare(Student s1, Student s2) {
                return s1.getAge() - s2.getAge(); // Sort by age
            }
        });

        System.out.println("After sorting by age: " + students);

        // Using lambda expression (Java 8 and later)
        Collections.sort(students, (s1, s2) -> s1.getName().compareTo(s2.getName()));

        System.out.println("After sorting by name using lambda: " + students);
    }
}

Concepts Behind the Snippet

Sorting a `Collection` involves arranging its elements in a specific order. The `Comparable` interface defines the natural ordering, while the `Comparator` interface provides custom ordering logic. The core concept is to implement a comparison logic that determines the relative order of two elements. Sorting algorithms (e.g., merge sort, quicksort used internally by `Collections.sort()`) are used to efficiently arrange the elements according to this comparison logic.

Real-Life Use Case

Consider an e-commerce application where you need to display products. You might need to sort products by price (low to high, high to low), by rating (highest rated first), or by popularity (most frequently purchased). Using `Comparator` allows you to easily implement these different sorting criteria without altering the `Product` class. Another example is sorting user accounts by creation date or last login time.

Best Practices

  • Use `Collections.sort()` for simple ascending order sorting of Lists containing `Comparable` elements.
  • Implement `Comparable` in your custom classes to define a natural ordering.
  • Use `Comparator` for custom sorting logic, especially when multiple sorting criteria are needed.
  • Be mindful of null values when implementing `compareTo()` or `compare()`. Handle them gracefully to avoid `NullPointerException`.
  • For complex sorting scenarios, consider using Java 8's streams API and the `sorted()` method, which provides a functional approach to sorting.

Interview Tip

When asked about sorting in Java, be prepared to discuss `Collections.sort()`, `Comparable`, and `Comparator`. Explain the differences between them and provide scenarios where each would be appropriate. Also, be prepared to write code implementing a custom `Comparator`. Understanding the underlying sorting algorithms (e.g., merge sort) is also beneficial. Discuss time complexity for sorting: the `Collections.sort` use a merge sort which is O(n log n).

When to Use Them

  • Use `Collections.sort()` when you need to sort a `List` in its natural order.
  • Use `Comparable` when you want to define the default way to compare objects of a class. This is the 'natural' way these object types should be compared.
  • Use `Comparator` when you need to sort objects based on a criterion different from their natural order or when you don't have control over the class definition. This is useful for sorting by multiple properties or in varying ways.

Memory Footprint

The memory footprint of sorting depends on the sorting algorithm used. `Collections.sort()` in Java typically uses a variant of merge sort, which has a space complexity of O(n) in the worst case. This means that the memory required grows linearly with the size of the collection being sorted. Consider the size of your collections when dealing with large datasets. In-place sorting algorithms like quicksort are O(log n) in space complexity, but quicksort is not stable.

Alternatives

Alternatives to `Collections.sort()` include:
  • **Java 8 Streams API:** The `stream().sorted()` method provides a functional approach to sorting.
  • **Arrays.sort():** If you have an array instead of a Collection, you can use `Arrays.sort()`.
  • **Custom Sorting Algorithms:** For specialized sorting needs or performance optimization, you could implement your own sorting algorithms (e.g., insertion sort, quicksort), but this is generally not necessary unless you have very specific requirements.

Pros and Cons of `Comparable` vs. `Comparator`

`Comparable`
  • Pros: Defines the natural order of a class, simplifies sorting with `Collections.sort(list)`.
  • Cons: Only one sorting criterion can be defined per class, requires modifying the class definition.
`Comparator`
  • Pros: Allows multiple sorting criteria without modifying the class, flexible and reusable.
  • Cons: Requires creating separate `Comparator` classes or lambda expressions, slightly more verbose.

← How to iterate over Collections? How to throw custom exceptions? →

FAQ

  • How do I sort a list in descending order?

    You can use `Collections.reverseOrder()` in conjunction with `Collections.sort()` to sort in descending order. Alternatively, you can use `Comparator.reverseOrder()` with a custom comparator. For example: `Collections.sort(myList, Collections.reverseOrder());` or implement your custom comparator by inversing the logic.
  • What happens if I try to sort a list containing null values?

    Attempting to sort a list containing null values without handling them will typically result in a `NullPointerException`. You need to handle nulls in your `compareTo()` or `compare()` method. For example, you might treat nulls as either the smallest or largest values.
  • How can I sort a list of custom objects based on multiple fields?

    You can create a `Comparator` that compares objects based on multiple fields. You can chain comparisons using `thenComparing()` or `thenComparingInt()`, `thenComparingDouble()`, etc. For example:
    Comparator.comparing(Student::getLastName).thenComparing(Student::getFirstName)
  • What is the time complexity of `Collections.sort()`?

    The time complexity of `Collections.sort()` for `List` implementations (like `ArrayList`) is typically O(n log n), where n is the number of elements in the list. This is because it uses a variant of merge sort, which provides good performance in most cases.