Sorting a small given/fixed number of values

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)

I am not an expert on this topic, but Sorting networks might be what you are looking for.

3 Likes

Yes, this is exactly right.

Here’s a sample implementation for 2, 3, and 4 elements:

In-place
func sort<T>(_ a: inout T, _ b: inout T, by areInIncreasingOrder: (T,T)->Bool) {
  if areInIncreasingOrder(b, a) { swap(&a, &b) }
}

func sort<T>(_ a: inout T, _ b: inout T, _ c: inout T, by areInIncreasingOrder: (T,T)->Bool) {
  sort(&a, &b, by: areInIncreasingOrder)
  sort(&a, &c, by: areInIncreasingOrder)
  sort(&b, &c, by: areInIncreasingOrder)
}

func sort<T>(_ a: inout T, _ b: inout T, _ c: inout T, _ d: inout T, by areInIncreasingOrder: (T,T)->Bool) {
  sort(&a, &b, by: areInIncreasingOrder)
  sort(&c, &d, by: areInIncreasingOrder)
  sort(&a, &c, by: areInIncreasingOrder)
  sort(&b, &d, by: areInIncreasingOrder)
  sort(&b, &c, by: areInIncreasingOrder)
}
In-place `Comparable`
func sort<T: Comparable>(_ a: inout T, _ b: inout T) {
  sort(&a, &b, by: <)
}

func sort<T: Comparable>(_ a: inout T, _ b: inout T,  _ c: inout T) {
  sort(&a, &b, &c, by: <)
}

func sort<T: Comparable>(_ a: inout T, _ b: inout T,  _ c: inout T, _ d: inout T) {
  sort(&a, &b, &c, &d, by: <)
}
Out-of-place
func sort<T>(_ a: T, _ b: T, by areInIncreasingOrder: (T,T)->Bool) -> (T, T) {
  var (x, y) = (a, b)
  sort(&x, &y, by: areInIncreasingOrder)
  return (x, y)
}

func sort<T>(_ a: T, _ b: T, _ c: T, by areInIncreasingOrder: (T,T)->Bool) -> (T, T, T) {
  var (x, y, z) = (a, b, c)
  sort(&x, &y, &z, by: areInIncreasingOrder)
  return (x, y, z)
}

func sort<T>(_ a: T, _ b: T, _ c: T, _ d: T, by areInIncreasingOrder: (T,T)->Bool) -> (T, T, T, T) {
  var (w, x, y, z) = (a, b, c, d)
  sort(&w, &x, &y, &z, by: areInIncreasingOrder)
  return (w, x, y, z)
}
Out-of-place `Comparable`
func sort<T: Comparable>(_ a: T, _ b: T) -> (T, T) {
  sort(a, b, by: <)
}

func sort<T: Comparable>(_ a: T, _ b: T, _ c: T) -> (T, T, T) {
  sort(a, b, c, by: <)
}

func sort<T: Comparable>(_ a: T, _ b: T, _ c: T, _ d: T) -> (T, T, T, T) {
  sort(a, b, c, d, by: <)
}
1 Like

Very nice!

For 3 elements specifically, you could also write something like this with a giant switch:

Alternative sort3 implementation
func sort3<T>(_ a: inout T, _ b: inout T, _ c: inout T, by areInIncreasingOrder: (T,T)->Bool) {
  let ab = areInIncreasingOrder(a, b)
  let ac = areInIncreasingOrder(a, c)
  let bc = areInIncreasingOrder(b, c)
  switch(ab, ac, bc) {
  case (false, false, false) /*c<b<a*/ : swap(&a, &c)
  case (false, false, true)  /*b<c<a*/ : swap(&a, &c); swap(&a, &b);
  case (false, true, false)  /*CYCLE*/ : fatalError()
  case (false, true, true)   /*b<a<c*/ : swap(&a, &b)
  case (true, false, false)  /*c<a<b*/ : swap(&a, &b); swap(&a, &c)
  case (true, false, true)   /*CYCLE*/ : fatalError()
  case (true, true, false)   /*a<c<b*/ : swap(&b, &c)
  case (true, true, true)    /*a<b<c*/ : break
  }
}

That’s a lot harder to reason about (at least for me), and you’d probably need to check swift.godbolt.org to see how each version optimizes.

1 Like

I might be missing something, but your latest version starts by doing three comparisons, and then I guess the switch has to do some more.

The best/lucky case for three elements should only require two comparisons, no?

if a <= b {
    if b <= c {
        // Ah, done!
    } else {
        // ...
    }
} else {
    // ...
}
1 Like

It makes 3 calls to areInIncreasingOrder, which might involve arbitrarily large amounts of work. Then it performs a switch over a 3-tuple of Bools, which could in theory be optimized quite well.

I’m not convinced that nesting the conditionals would actually be a win, given the nature of modern processor execution. I suspect branchless compare-and-swap will be most efficient, though again you’d need to look at the optimized compiled output for each version to see what looks best.

1 Like

And while doing so, remember to watch out / search for, isolate and report any missed optimizations caused by the exact formulation (including seemingly irrelevant context) of your benchmarking code.
: )

Terms of Service

Privacy Policy

Cookie Policy