Sorting a Swift array by ordering from another array

Edit: My original approach was shit. This post got a lot of traction, so it's time to give it some more attention and improve it.

Fundamentally, the problem is easy. We have two elements, and we have an array (or any ordered Collection) whose relative ordering determines their sort order. For every element, we find its position in the ordered collection, and compare the two indices to determine which is "greater".

However, if we naively do linear searches (e.g. Array.firstIndex(of:)), we'll get really bad performance (O(array.count)), particularly if the fixed ordering is very large. To remedy this, we can construct a Dictionary, that maps elements to their indices. The dictionary provides fast O(1) look-ups, which is perfect for the job.

This is exactly what HardCodedOrdering does. It pre-computes a dictionary of elements to their orderings, and provides an interface to compare 2 elements. Even better, it can be configured to respond differently to encountering elements with an unknown ordering. It could put them first before everything else, last after everything else, or crash entirely (the default behaviour).

HardCodedOrdering

public struct HardCodedOrdering<Element> where Element: Hashable {    public enum UnspecifiedItemSortingPolicy {        case first        case last        case assertAllItemsHaveDefinedSorting    }    private let ordering: [Element: Int]    private let sortingPolicy: UnspecifiedItemSortingPolicy    public init(        ordering: Element...,        sortUnspecifiedItems sortingPolicy: UnspecifiedItemSortingPolicy = .assertAllItemsHaveDefinedSorting    ) {        self.init(ordering: ordering, sortUnspecifiedItems: sortingPolicy)    }    public init<S: Sequence>(        ordering: S,        sortUnspecifiedItems sortingPolicy: UnspecifiedItemSortingPolicy = .assertAllItemsHaveDefinedSorting    ) where S.Element == Element {        self.ordering = Dictionary(uniqueKeysWithValues: zip(ordering, 1...))        self.sortingPolicy = sortingPolicy    }    private func sortKey(for element: Element) -> Int {        if let definedSortKey = self.ordering[element] { return definedSortKey }        switch sortingPolicy {            case .first:    return Int.min            case .last:     return Int.max            case .assertAllItemsHaveDefinedSorting:                fatalError("Found an element that does not have a defined ordering: \(element)")        }    }    public func contains(_ element: Element) -> Bool {        return self.ordering.keys.contains(element)    }    // For use in sorting a collection of `T`s by the value's yielded by `keyDeriver`.    // A throwing varient could be introduced, if necessary.    public func areInIncreasingOrder<T>(by keyDeriver: @escaping (T) -> Element) -> (T, T) -> Bool {        return { lhs, rhs in            self.sortKey(for: keyDeriver(lhs)) < self.sortKey(for: keyDeriver(rhs))        }       }    // For use in sorting a collection of `Element`s    public func areInIncreasingOrder(_ lhs: Element, rhs: Element) -> Bool {                return sortKey(for: lhs) < sortKey(for: rhs)    }}

Example usage:

let rankOrdering = HardCodedOrdering(ordering: "Private", "Lieutenant", "Captain", "Admiral") // ideally, construct this once, cache it and share itlet someRanks = [    "Admiral", // Should be last (greatest)    "Gallactic Overlord", // fake, should be removed    "Private", // Should be first (least)]let realRanks = someRanks.lazy.filter(rankOrdering.contains)let sortedRealRanks = realRanks.sorted(by: rankOrdering.areInIncreasingOrder) // works with mutating varient, `sort(by:)`, too.print(sortedRealRanks) // => ["Private", "Admiral"]

Here's a generic Swift 5.2 solution.

First we need to define a protocol that holds a property that is used to reorder our elements:

protocol Reorderable {    associatedtype OrderElement: Equatable    var orderElement: OrderElement { get }}

Then we need to extend Array with elements conforming to Reorderable and implement our reordering function:

extension Array where Element: Reorderable {    func reorder(by preferredOrder: [Element.OrderElement]) -> [Element] {        sorted {            guard let first = preferredOrder.firstIndex(of: $0.orderElement) else {                return false            }            guard let second = preferredOrder.firstIndex(of: $1.orderElement) else {                return true            }            return first < second        }    }}

Example

Let's assume you have defined:

struct Player {    let position: String}let currentPositions = ["RB", "AA", "BB", "CC", "WR", "TE"]let players = currentPositions.map { Player(position: $0) }

Now, all you need to do is conform Player to Reorderable:

extension Player: Reorderable {    typealias OrderElement = String    var orderElement: OrderElement { position }}

You can now use:

let sortedPlayers = players.reorder(by: ["QB", "WR", "RB", "TE"])print(sortedPlayers.map { $0.position })// ["WR", "RB", "TE", "AA", "BB", "CC"]

Original Solution

This is a generic Swift 5.2 solution based on OuSS' code and requires array elements to be Equatable.

extension Array where Element: Equatable {    func reorder(by preferredOrder: [Element]) -> [Element] {        return self.sorted { (a, b) -> Bool in            guard let first = preferredOrder.firstIndex(of: a) else {                return false            }            guard let second = preferredOrder.firstIndex(of: b) else {                return true            }            return first < second        }    }}let currentPositions = ["RB", "AA", "BB", "CC", "WR", "TE"]let preferredOrder = ["QB", "WR", "RB", "TE"]let sorted = currentPositions.reorder(by: preferredOrder)print(sorted) // ["WR", "RB", "TE", "AA", "BB", "CC"]

Based on Alexander's answer, I've implemented an extension to do this.

extension Array where Element == String {func reordered() -> [String] {    let defaultOrder = ["orange", "pear", "watermelon", "grapefruit", "apple", "lemon", "tomatoes"]    return self.sorted { (a, b) -> Bool in        if let first = defaultOrder.index(of: a), let second = defaultOrder.index(of: b) {            return first < second        }        return false    }}let arrayToSort = ["lemon", "watermelon", "tomatoes"]let sortedArray = arrayToSort.reordered()print(sortedArray) // ["watermelon", "lemon", "tomatoes"]