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 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"]
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"]
What I will do:
- 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.
- Loop through your
positionOrdersand 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)")
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