Let's say we want to make sure that a small number of separate values/variables/constants (ie not an Array) are ordered (because eg the remaining code becomes easier to write if a b and c are known to be in ascending order).
For two elements it's just:
let (a, b) = p > q ? (q, p) : (p, q)
or ( for mutable p q ):
if p > q { swap(&p, &q) }
For three elements it's not as straight forward, but if we know that our code won't be executed super frequently and just want to get it done, we might write something like:
let tmpAr = [p, q, r].sorted()
let (a, b, c) = (tmpAr[0], tmpAr[1], tmpAr[2])
or ( for mutable p q r ):
if p > q { swap(&p, &q) }
if q > r { swap(&q, &r) }
if p > q { swap(&p, &q) }
It's a lot of code for something as simple as that, it might be hard to spot a mistake in it and if efficiency matters we would need to spend some more time on improving it.
More than a couple of times, I've found myself needing this kind of sorting (for 3 or 4 elements).
Here's an example, for 2 and 3 values.
extension Disk {
/// Returns the smallest disk enclosing two other disks `a` and `b`.
init(smallestDiskEnclosing a: Disk, and b: Disk) {
// Start by sorting the disks by ascending radius, smallest first:
let (a, b) = a.radius < b.radius ? (a, b) : (b, a)
let cDist = simd_distance(a.center, b.center)
// If one of the disks (b) encloses the other (a), we are done:
guard cDist + a.radius > b.radius else { self = b; return }
let enclosingDiskR = (cDist + a.radius + b.radius) * 0.5
let t = (enclosingDiskR - a.radius) / cDist
self = Disk(center: simd_mix(a.center, b.center, .init(t, t)),
radius: enclosingDiskR)
}
/// Returns the smallest disk enclosing three other disks `a`, `b`, and `c`.
init(smallestDiskEnclosing a: Disk, b: Disk, and c: Disk) {
// Start by sorting the disks by ascending radius, smallest first:
let (a, b, c) = ...
// ...
}
/// Returns the smallest disk enclosing a sequence of disks.
init(smallestDiskEnclosing: S) where S: Sequence, S.Element == Disk {
// Problem is solved recursively (terminal case is 3 disks or less) ...
// ...
}
}
It would be nice to solve this once and for all, and why not in the form of a group challenge here?
Challange:
Come up with something that makes this kind of sorting, for 2, 3 and 4 elements (of the same type), nice and efficient!
Ideally, it should probably support both immutable and mutable (inout) usage, perhaps even unsafe usage on raw memory (for sorting eg successive chunks of four Float values in a big memory block).
I haven't thought much about design, but perhaps something like this on the call site:
let (a, b, c) = sorted(p, q, r) // ascending order
let (a, b, c) = sorted(p, q, r, by: >) // descending order
sort(&p, &q, &r)
sort(&p, &q, &r, by: >)
and maybe even something like:
sort4(elementsOfType: Float.self, startingAt: ptr)