TypeScript, lesson 12
Sorting and searching come up everywhere: leaderboards, price lists, finding the right bracket
for a value. JavaScript's built-in sort does the heavy lifting; TypeScript makes sure the
compare function you hand it fits the data.
Without arguments, sort converts elements to strings, so numbers come out in dictionary
order. Always pass a compare function (a, b) => number for anything but plain strings:
a goes first;b goes first;For strings, a.localeCompare(b) returns the right kind of number and handles accents and
case sensibly.
2 exercises to try what you just read.
sort reorders the array in place and returns it. When you want to keep the original,
use toSorted, which returns a sorted copy.
Because products below is a Product[], TypeScript infers that a and b are Product,
and it will flag a typo such as a.prise:
|| moves on to the next key only when the previous comparison gave 0 (a tie).
You can also store comparators in a typed table and choose one at run time:
Unsorted data is searched one element at a time: includes, indexOf, find (returns
T | undefined, so TypeScript makes you handle "not found"), and findIndex (returns -1).
Sorted data allows binary search. Compare the target with the middle element, then throw away the half where it cannot be. Every step halves the remaining range, so a million elements take about twenty steps.
A very useful variant is the lower bound: the first index whose element is greater than or equal to the target. It answers "where would this go?" and "which bracket does this fall into?":
The range is lo up to but not including hi, and the loop keeps the answer inside it until
lo and hi meet. If sorted[lowerBound(...)] equals the target, the value is present.
The first input line is a sort order: price, rating or name. Every following line is a
product: NAME PRICE RATING. Print the products sorted by the chosen order, one per line as
NAME PRICE RATING:
price: cheapest first;rating: highest rating first;name: alphabetical.For price and rating, break ties alphabetically by name. Names are single lower-case words
and are unique.
Sample input:
Sample output:
A courier charges by weight bracket. The first input line lists the upper weight limits of the
brackets in kilograms, in increasing order. The second line lists the price for each bracket.
A parcel belongs to the first bracket whose limit is greater than or equal to its weight.
Every remaining line is a parcel weight; print W kg: PRICE or W kg: too heavy when it is
above every limit.
Write lowerBound(sorted: number[], target: number): number with binary search and use it to
find the bracket.
Sample input:
Sample output:
const scores = [10, 9, 100, 1];
scores.sort();
console.log(scores); // [ 1, 10, 100, 9 ] (compared as text!)scores.sort((a, b) => a - b); // ascending
scores.sort((a, b) => b - a); // descendinginterface Product {
name: string;
price: number;
rating: number;
}
const products: Product[] = [
{ name: "lamp", price: 30, rating: 4 },
{ name: "desk", price: 120, rating: 5 },
{ name: "chair", price: 30, rating: 5 },
];
// cheapest first; equal prices: best rating first; then by name
products.sort((a, b) =>
a.price - b.price || b.rating - a.rating || a.name.localeCompare(b.name)
);type Compare<T> = (a: T, b: T) => number;
const orders: Record<string, Compare<Product>> = {
price: (a, b) => a.price - b.price,
name: (a, b) => a.name.localeCompare(b.name),
};function lowerBound(sorted: number[], target: number): number {
let lo = 0;
let hi = sorted.length; // the answer may be "after everything"
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (sorted[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
lowerBound([10, 20, 30], 20); // 1
lowerBound([10, 20, 30], 25); // 2
lowerBound([10, 20, 30], 99); // 3 (past the end)price
lamp 30 4
desk 120 5
chair 30 5chair 30 5
lamp 30 4
desk 120 51 5 10 30
4.5 9 15 40
0.4
5
12
310.4 kg: 4.5
5 kg: 9
12 kg: 40
31 kg: too heavy