Practice: a race leaderboard

record Result(String name, double seconds) {}

String fastestName(ArrayList<Result> results) {
    Result best = results.get(0);
    for (Result result : results) {
        if (result.seconds() < best.seconds()) {
            best = result;
        }
    }
    return best.name();
}

void main() {
    ArrayList<Result> results = new ArrayList<>(List.of(
            new Result("Nadia", 58.2),
            new Result("Omar", 61.0),
            new Result("Priya", 57.4),
            new Result("Quinn", 63.5)));
    IO.println(fastestName(results));
}

Fastest is the smallest time, so the comparison is <. Everything about a race says "best" and means "least."

record Result(String name, double seconds) {}

ArrayList<Result> ranked(ArrayList<Result> results) {
    ArrayList<Result> sorted = new ArrayList<>(results);
    sorted.sort(Comparator.comparing(result -> result.seconds()));
    return sorted;
}

void main() {
    ArrayList<Result> results = new ArrayList<>(List.of(
            new Result("Nadia", 58.2),
            new Result("Omar", 61.0),
            new Result("Priya", 57.4),
            new Result("Quinn", 63.5)));
    for (Result result : ranked(results)) {
        IO.println(result.name() + " " + result.seconds());
    }
    IO.println("Handed in first: " + results.get(0).name());
    IO.println(ranked(new ArrayList<>()));
    IO.println(ranked(new ArrayList<>(List.of(
            new Result("Omar", 61.0),
            new Result("Priya", 57.4)))));
}

The comparator sorts on each result's time. Sorting a copy leaves the clipboard's own list in the order the results were handed in, which is why Handed in first: still names Nadia.

record Result(String name, double seconds) {}

ArrayList<Result> ranked(ArrayList<Result> results) {
    ArrayList<Result> sorted = new ArrayList<>(results);
    sorted.sort(Comparator.comparing(result -> result.seconds()));
    return sorted;
}

int placeOf(ArrayList<Result> results, String name) {
    ArrayList<Result> order = ranked(results);
    for (int i = 0; i < order.size(); i++) {
        if (order.get(i).name().equals(name)) {
            return i + 1;
        }
    }
    return -1;
}

void main() {
    ArrayList<Result> results = new ArrayList<>(List.of(
            new Result("Nadia", 58.2),
            new Result("Omar", 61.0),
            new Result("Priya", 57.4),
            new Result("Quinn", 63.5)));
    IO.println(placeOf(results, "Priya"));
    IO.println(placeOf(results, "Zed"));
}

The place is the index in the ranked list plus one: nobody finishes in place 0. Names are compared with .equals, and -1, which no place can be, means the name did not run.

record Result(String name, double seconds) {}

Result resultFor(ArrayList<Result> results, String name) {
    for (Result result : results) {
        if (result.name().equals(name)) {
            return result;
        }
    }
    return null;
}

void main() {
    ArrayList<Result> results = new ArrayList<>(List.of(
            new Result("Nadia", 58.2),
            new Result("Omar", 61.0),
            new Result("Priya", 57.4),
            new Result("Quinn", 63.5)));
    IO.println(resultFor(results, "Omar"));
    IO.println(resultFor(results, "Zed"));
}

The whole record, not the name that was passed in, so the caller gets the time as well. A binary search is no use here: the list is not sorted by name. null after the loop says that no runner matched.

int insertionPoint(double[] times, double target) {
    int low = 0;
    int high = times.length;
    while (low < high) {
        int middle = (low + high) / 2;
        if (times[middle] < target) {
            low = middle + 1;
        } else {
            high = middle;
        }
    }
    return low;
}

void main() {
    double[] times = {57.4, 58.2, 61.0};
    IO.println(insertionPoint(times, 60.0));
    IO.println(insertionPoint(times, 58.2));
}

high starts at times.length, one past the end, because a time slower than all of them goes there. times[middle] < target rather than <= is what puts an equal time before the one already there: the two versions differ only on that case, which is why it is tested. The loop's own test, while (low < high), is right here because high starts one past the end, so the range is empty when low reaches it; in the chapter's loop high is the last index, which is why that loop needs <=.

record Result(String name, double seconds) {}

ArrayList<Result> ranked(ArrayList<Result> results) {
    ArrayList<Result> sorted = new ArrayList<>(results);
    sorted.sort(Comparator.comparing(result -> result.seconds()));
    return sorted;
}

ArrayList<String> podium(ArrayList<Result> results) {
    ArrayList<String> names = new ArrayList<>();
    for (Result result : ranked(results)) {
        if (names.size() < 3) {
            names.add(result.name());
        }
    }
    return names;
}

void main() {
    ArrayList<Result> results = new ArrayList<>(List.of(
            new Result("Nadia", 58.2),
            new Result("Omar", 61.0),
            new Result("Priya", 57.4),
            new Result("Quinn", 63.5)));
    IO.println(podium(results));
}

The loop adds a name only while there are fewer than three, so a race of two gives back two, and no position past the end is ever asked for.

double[] sortTimes(double[] times) {
    double[] out = Arrays.copyOf(times, times.length);
    for (int i = 1; i < out.length; i++) {
        double current = out[i];
        int j = i - 1;
        while (j >= 0 && out[j] > current) {
            out[j + 1] = out[j];
            j--;
        }
        out[j + 1] = current;
    }
    return out;
}

void main() {
    double[] times = {61.0, 57.4, 58.2};
    IO.println(Arrays.toString(sortTimes(times)));
    IO.println(Arrays.toString(times));
    IO.println(Arrays.toString(sortTimes(new double[] {3.0, 1.0, 2.0, 5.0, 4.0})));
    IO.println(Arrays.toString(sortTimes(new double[] {1.0})));
    IO.println(Arrays.toString(sortTimes(new double[] {2.0, 1.0})));
    IO.println(Arrays.toString(sortTimes(new double[] {})));
}

This is Try It 4's insertion sort, on a copy, so the array handed in keeps its order. After the while loop stops, j has gone one too far, so the time belongs at j + 1. Putting it at j is the classic off-by-one here.

record Result(String name, double seconds) {}

ArrayList<Result> ranked(ArrayList<Result> results) {
    ArrayList<Result> sorted = new ArrayList<>(results);
    sorted.sort(Comparator.comparing(result -> result.seconds()));
    return sorted;
}

ArrayList<String> leaderboardLines(ArrayList<Result> results) {
    ArrayList<String> lines = new ArrayList<>();
    ArrayList<Result> order = ranked(results);
    for (int i = 0; i < order.size(); i++) {
        Result result = order.get(i);
        lines.add((i + 1) + ". " + result.name() + " " + result.seconds());
    }
    return lines;
}

void main() {
    ArrayList<Result> results = new ArrayList<>(List.of(
            new Result("Nadia", 58.2),
            new Result("Omar", 61.0),
            new Result("Priya", 57.4),
            new Result("Quinn", 63.5)));
    for (String line : leaderboardLines(results)) {
        IO.println(line);
    }
}

Rank first, then number. Numbering the clipboard order gives everyone a place and gets all of them wrong.