Part 18: Algorithms
From here on the course tours the standard packages, and it starts with the one every program reaches for sooner or later. The Algorithms package is a set of generic functions over slices: sort them, search them, find their extremes, fold them into one answer. Because every function takes a slice, one function serves an array of any length, part of an array, or the contents of a collection — and none of them ever allocates memory.
What you will learn
- Sorting a slice in place through a writable view, by the element's own
<or by an order function of yours. - Searching any slice from the front, and handling the
nonethat "not found" is. - Searching sorted data in logarithmic time, and the promise that comes with it.
- The smaller of two values, and the position of the smallest in a slice — which may not exist.
- Collapsing a slice into one answer with
Foldand a step function.
Which function?
flowchart LR
q(["What do you want<br/>from a slice?"]) --> order["to put it in order"]
q --> find["to find a value"]
q --> ext["its smallest or<br/>largest element"]
q --> one["one answer<br/>from every element"]
order --> sort["Sort, SortDescending, SortBy<br/>(18.1)"]
find --> sorted{"is it sorted?"}
sorted -- "no, or not sure" --> lin["IndexOf, LastIndexOf, Contains<br/>(18.2)"]
sorted -- "yes" --> bin["BinarySearch, LowerBound, UpperBound<br/>(18.3)"]
ext --> mm["MinIndex, MaxIndex<br/>(18.4)"]
one --> fold["Fold, FoldRight<br/>(18.5)"]The functions share a few habits, and knowing them makes the rest of the package predictable:
| Habit | Functions in this part |
|---|---|
Take a writable view, var T[..], and change it | Sort, SortDescending, SortBy |
Answer with uint?, none when there is no answer | IndexOf, LastIndexOf, BinarySearch, MinIndex, MaxIndex |
| Always have an answer | Contains, LowerBound, UpperBound, Min, Max, Fold |
| Take a named function for the part that varies | SortBy, Fold, FoldRight |
Lessons
| Lesson | What you will learn | |
|---|---|---|
| 18.1 | Sort | sort a slice in place |
| 18.2 | Search | find a value in a slice, and handle not finding it |
| 18.3 | Binary search | find a value in sorted data quickly |
| 18.4 | Min and max | the smallest and largest values, and the empty case |
| 18.5 | Fold | combine all elements into one value with a function |
Before you start
The lessons lean on Slice and Writable slice from Part 5, Callback and Generic from Part 4, Presence and Coalesce from Part 8: Optionals, and Comparable from Part 12. Each lesson's package is in the Examples repository's Algorithms/ folder:
cd Examples/Algorithms/Sort
rux run
After this part
The checkpoint project Statistics puts the whole part to work: it sorts, finds extremes and folds slices of numbers into a count, a mean, a variance and a median, including the awkward cases of one value and none. Then Part 19: Files leaves memory behind and reads and writes the disk.
For the rules underneath this part, see Slices, Function types and Generic functions in the Rux Reference.