Java, lesson 12
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.
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.
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.
intPlayer::scorep -> 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.
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.
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 30static 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 101. al 50
2. bea 30
3. zoe 30
4. cy 103 8 15 23 42 99
23
4
3Found at 3
Not found
Found at 0