1

I have lists of tasks that I want to sort pseudo-topologically. Say, I have something like this:

enum Task {
    case a(Int, Int)
    case b(String)
    case c(Bool)
}

I require all a tasks to be executed before any b tasks, and all b tasks before all c tasks. In addition, all tasks of the same time need to remain in the same order as in the input.

In computer science lingo, what I need is

  • a stable sorting algorithm and
  • a way to feed it a partial order.

Is there such a thing in the Swift standard library?

Observations:

  • Comparable, a natural protocol to look at for sorting, requires the order to be total.
  • sorted can be made to work with partial orders, but is not stable.

As an alternative, a topological sorting algorithm would work as well, even though it would do more than I need.

Raphael
  • 9,779
  • 5
  • 63
  • 94
  • 2
    I am probably missing something, but why can't you define a total order on your type? – Any "a" value is equal to any other "a" value, and less than any "b" value, etc. – Martin R Sep 20 '17 at 15:00
  • @MartinR I *could* do that if I abused `==` that way. As soon as I need `==` for _real_ equality, implementing `<` as partial order would break the invariants required by `Comparable`. – Raphael Sep 20 '17 at 15:09
  • I'm afraid not. IIRC, the standard library's sorting algorithms *happen* to be stable, but the documentation explicitly states that there's no guarentee they will be stable. – Alexander Sep 20 '17 at 15:15
  • @Alexander: The Collection sort method uses Introsort (a variant of Quicksort), which is not stable as far as I know. – Martin R Sep 20 '17 at 15:20

0 Answers0