Learn/Java/12. Sorting and searching
Lesson 12 of 15
Sign in

Java, lesson 12

Sorting and searching

Sorted data is easier for people to read and much faster for programs to search. Java's libraries sort for you; your job is to say what order you want.

Sorting in natural order

Numbers sort smallest first and strings sort alphabetically (by character code, so uppercase letters come before lowercase):

Arrays.sort sorts an array in place; list.sort(...) sorts a list in place. Sorting objects is stable: items that compare as equal keep their original relative order.

Custom order with Comparator

A Comparator<T> decides which of two items comes first. You rarely write one by hand; you build it from small pieces with lambdas and method references:

  • Comparator.comparing(keyExtractor) sorts by a key; comparingInt is the version for keys. is a , shorthand for the lambda .

2 exercises to try what you just read.

Exercise 1

Leaderboard

Press Ctrl Enter or Check to test your code.

Exercise 2

Price finder

Press Ctrl Enter or Check to test your code.

int
Player::score
method reference
p -> p.score()
  • .reversed() flips the order of everything built so far.
  • .thenComparing(...) breaks ties with a second key.
  • Read the chain left to right: "by score, highest first, then by name".

    A class can also define its own natural order by implementing Comparable<T> and its compareTo method, which returns a negative number, zero or a positive number. Comparators are more flexible, because one type can be sorted many ways.

    Searching: linear versus binary

    To find a value in an unsorted list you must check every element: that is a linear search, and list.indexOf(x) does exactly that. For a million items, that is up to a million checks.

    If the data is sorted, binary search is dramatically faster. Look at the middle element: if it is the target, you are done; if the target is smaller, it can only be in the left half; otherwise, the right half. Each step halves the remaining range, so a million items need only about 20 steps.

    The library versions are Arrays.binarySearch(array, key) and Collections.binarySearch(list, key). When the key is missing, they return a negative number that encodes where it would be inserted: -(insertionPoint) - 1. Binary search on unsorted data gives meaningless answers, so always sort first.

    Further reading

    • Writing and combining comparators (dev.java)
    • Arrays API (sort, binarySearch)
    • Comparator API

    The first line is a number N, followed by N lines of name score. Print the leaderboard: the highest score first, and players with equal scores in alphabetical order of their names. Each line is <rank>. <name> <score>, where rank is simply the position 1, 2, 3, …

    Sample input:

    Sample output:

    The first line holds distinct whole-number prices in ascending order, separated by spaces. Each following line is a price to look up. Write your own static int binarySearch(int[] a, int target) (do not use Arrays.binarySearch) and, for each query, print Found at <index> (index counted from 0) or Not found.

    Sample input:

    Sample output:

    int[] scores = {42, 7, 19};
    Arrays.sort(scores);                       // [7, 19, 42]
    
    List<String> names = new ArrayList<>(List.of("mia", "Leo", "ana"));
    Collections.sort(names);                   // [Leo, ana, mia]
    names.sort(String.CASE_INSENSITIVE_ORDER); // [ana, Leo, mia]
    record Player(String name, int score) { }
    
    List<Player> players = new ArrayList<>(List.of(
        new Player("Zoe", 30), new Player("Al", 50), new Player("Bea", 30)));
    
    players.sort(Comparator.comparingInt(Player::score));
    // Zoe 30, Bea 30, Al 50   (ties keep their input order)
    
    players.sort(Comparator.comparingInt(Player::score).reversed()
                           .thenComparing(Player::name));
    // Al 50, Bea 30, Zoe 30
    static int binarySearch(int[] a, int target) {
        int low = 0;
        int high = a.length - 1;
        while (low <= high) {
            int mid = (low + high) >>> 1;   // middle index, safe from overflow
            if (a[mid] == target) return mid;
            if (a[mid] < target) low = mid + 1;
            else high = mid - 1;
        }
        return -1;                           // not found
    }
    4
    zoe 30
    al 50
    bea 30
    cy 10
    1. al 50
    2. bea 30
    3. zoe 30
    4. cy 10
    3 8 15 23 42 99
    23
    4
    3
    Found at 3
    Not found
    Found at 0