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