Sorting a Swift array by ordering from another array

Question

Say I have an array of the custom class [Player], each of which contains a string property called player.position

I also have an arbitrary array of values, called positionOrders, like so:

let positionOrders = ["QB", "WR", "RB", "TE"]

Where my goal is to sort the [Player] to have all the "QB"s first, then "WR"s, "RB"s, and finally "TE"s.

The current way I am doing loops through each element in positionOrders, then inside that loops through all the players to append to a new array. However, I could not figure a simpler (and more efficient) way to do this. Any tips or pointers are much appreciated. Thanks.

Answer 1

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 it

let 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"]

Answer 2

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"]

Answer 3

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"]

Answer 4

SwifterSwift has this implementation

/// SwifterSwift: Sort an array like another array based on a key path. If the other array doesn't contain a certain value, it will be sorted last.
    ///
    ///        [MyStruct(x: 3), MyStruct(x: 1), MyStruct(x: 2)].sorted(like: [1, 2, 3], keyPath: \.x)
    ///            -> [MyStruct(x: 1), MyStruct(x: 2), MyStruct(x: 3)]
    ///
    /// - Parameters:
    ///   - otherArray: array containing elements in the desired order.
    ///   - keyPath: keyPath indiciating the property that the array should be sorted by
    /// - Returns: sorted array.
    func sorted<T: Hashable>(like otherArray: [T], keyPath: KeyPath<Element, T>) -> [Element] {
        let dict = otherArray.enumerated().reduce(into: [:]) { $0[$1.element] = $1.offset }
        return sorted {
            guard let thisIndex = dict[$0[keyPath: keyPath]] else { return false }
            guard let otherIndex = dict[$1[keyPath: keyPath]] else { return true }
            return thisIndex < otherIndex
        }
    }

Answer 5

What I will do:

1. Create a Dictionary with position as the Key, and an Array of players in that position as the Value. O(n), where n is the number of players.
2. Loop through your positionOrders and fetch Value to each Key(position).

Here is the code:

    let preSortPlayerList = [Player]() // Filled with your players.
    let positionOrders = ["QB", "WR", "RB", "TE"]
    let dict = preSortPlayerList.reduce([String : [Player]]()) {
        var map = $0
        if var tmp = map[$1.position] {
            tmp.append($1)
            map[$1.position] = tmp
        } else {
            map[$1.position] = [$1]
        }
        return map
    }

    let playersArray: [Player] = positionOrders.flatMap { dict[$0] ?? [Player]() }
    print("\(playersArray)")

Answer 6

It's incredibly simple:

positionOrders.filter{player.contains($0)}

That's all there is to it.

An even more obvious approach:

The way you sort something is simply like this:

    player.sort{
        .. your formula for sorting goes here
    }

For example if you want to sort by "bank balance"

    player.sort{
        $0.bankBalance < $1.bankBalance
    }

To sort by "another array", it's just

    player.sort{
        let i = positionOrders.firstIndex(of: $0) ?? 0
        let j = positionOrders.firstIndex(of: $1) ?? 0
        return i < j
    }

That's all there is to it.

(Note that obviously you'd just use Int.max rather than the 0 if you wanted "missing" items to appear at the end rather than the start, if missing items are conceivable in your use case.)

---

(Note that the comments on this page about performance are off the mark by many, many orders of magnitude. It's inconceivable performance could be an issue in the milieu stated. If, incredibly, beyond all belief, performance is an issue you just do the obvious, add a line of code to hash the indexes. Take care though, making a hash is actually !!LESS PERFORMANT!! in almost all cases. Again, just TBC, it's incredibly unlikely performance will be an issue; use the code above)

Answer 7

For swift 4

Very simple way and diligent( feel free to suggest and correct me )

func reOrder(array : [String] , order : [String]) -> [String]{ 

    //common elments in order
    // order.filter{array.contains($0)}

    // the rest of the array that the order doesnt specify
    // array.filter{!order.contains($0)}

 return order.filter{array.contains($0)} + array.filter{!order.contains($0)}
}


let list =     ["A", "Z", "B", "H", "C", "T", "D", "E"] 
let newOrder = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L"]




print("The ordered list is ",reOrder(array: list, order: newOrder))


 // The ordered list is  ["A", "B", "C", "D", "E", "H", "Z", "T"]

it would be good if someone can make it as extension for Generic type, I'm not good with that

Answer 8

I love one-liners and here is another one:

positionOrders.compactMap { order in players.first(where: { $0.position == order })}

Only thing to consider about this approach is that it will have the O(n*m) - or O(positionOrders*players) - time complexity.

Answer 9

Based on Emily code, i did some change to extension cause it will not make the elements that doesn't exist in defaultOrder at the end

extension Array where Element == String {

func reordered() -> [String] {

    let defaultOrder = ["lemon", "watermelon", "tomatoes"]

    return self.sorted { (a, b) -> Bool in
        guard let first = defaultOrder.index(of: a) else {
            return false
        }

        guard let second = defaultOrder.index(of: b) else {
            return true
        }

        return first < second
    }
}

let arrayToSort = ["orange", "watermelon", "grapefruit", "lemon", "tomatoes"]
let sortedArray = arrayToSort.reordered()
print(sortedArray) // ["watermelon", "lemon", "tomatoes", "orange", "grapefruit"]

Answer 10

Since iOS15, we can use SortComparator to help us sort the objects with custom logic easily.

e.g. A SortComparator that sorts players by predefined position order. If the position isn't included in the order, sort by the player ID instead.

struct Player: Equatable {
    let id: Int
    let position: String
}

struct PlayerSort: SortComparator {
    let positionOrder: [String: Int]
    var order: SortOrder
    
    init(positionOrder: [String]) {
        self.order = .forward
        var order = [String: Int]()
        positionOrder.enumerated().forEach {
            order[$1] = $0
        }
        self.positionOrder = order
    }

    func compare(_ lhs: Player, _ rhs: Player) -> ComparisonResult {
        if positionOrder[lhs.position] ?? Int.max < positionOrder[rhs.position] ?? Int.max {
            return .orderedAscending
        } else if positionOrder[lhs.position] ?? Int.max > positionOrder[rhs.position] ?? Int.max {
            return .orderedDescending
        } else {
            return KeyPathComparator(\Player.id).compare(lhs, rhs)
        }
    }
}

Usage

[player1, player2, player3, player4, player5].sorted(using: PlayerSort(positionOrder: ["QB", "WR", "RB", "TE"]))

Docs:

1. https://developer.apple.com/documentation/foundation/sortcomparator
2. https://useyourloaf.com/blog/sortcomparator-and-sortdescriptor/