efficient sorting of an array based on another array's order

Question

Suppose I have this:

struct Pet {
 let name: String
}
let pets = [Pet(name: "Z"), Pet(name: "F"), Pet(name: "A"), Pet(name: "E")]
let petNames = ["E", "F", "Z", "A"]

and my intended output is:

[Pet(name: "E"), Pet(name: "F"), Pet(name: "Z"), Pet(name: "A")]

How do I sort pets efficiently by following petNames' order?

My current method appears to be horribly inefficient:

var sortedPets = [Pet]()
for n in petNames {
 sortedPets.append(pets.first(where: { return 0ドル.name == n })!)
}

Any functional approach that I could use?

• OOPer: This thread is similar to yours.
• Tj3n: Create new array based on the other array indeed seems to be much faster than try to sort it
• Alexander: @Tj3n Not in the general case, but that's possible for such a short input array and sorted order array

Answer 1

Not efficient, but it solves the problem functionally:

let pets2 = pets.sorted{petNames.index(of:0ドル.name)! < petNames.index(of:1ドル.name)!}

Now that we know what we're after, this is more elaborate but much more efficient, because dictionary lookup is fast:

var d = [String:Int]()
zip(petNames, 0..<petNames.count).forEach { d[0ドル.0] = 0ドル.1 }
let pets2 = pets.sorted{d[0ドル.name]! < d[1ドル.name]!}

Answer 2

I have written an extension just for this. It's pretty flexible, in that it lets you define by what field the input is sorted, and how to handle elements whose sort ordering isn't defined according to the sortingOrder list.

It's pretty long, so I suggest you tuck it away in its own file:

enum UnspecifiedItemSortingPolicy {
 case first
 case last
 case omitEntirely
 case assertAllItemsHaveDefinedSorting
}
extension MutableCollection {
 typealias Element = Iterator.Element
 func sorted<T: Equatable>(
 byOrderOf sortingMemberDeriver: @escaping (Element) -> T,
 in sortingOrder: [T],
 sortUnspecifiedItems unspecifiedItemSortingPolicy: UnspecifiedItemSortingPolicy = .assertAllItemsHaveDefinedSorting
 ) -> [Element] {
 switch unspecifiedItemSortingPolicy {
 case .omitEntirely: return self
 .lazy
 .map { (element: Element) -> (element: Element, position: Int) in
 let sortingMember = sortingMemberDeriver(element)
 guard let position = sortingOrder.index(of: sortingMember) else {
 fatalError("Attempted to sort a collection (\(self)) containing an item (\(element)) whose ordering was not defined in the sorting order: \(sortingOrder).")
 }
 return (element: element, position: position)
 }
 .sorted{ 0ドル.position < 1ドル.position }
 .map{ 0ドル.element }
 case .assertAllItemsHaveDefinedSorting: return self
 .lazy
 .flatMap { (element: Element) -> (element: Element, position: Int)? in
 let sortingMember = sortingMemberDeriver(element)
 return sortingOrder.index(of: sortingMember).map{ (element: element, position: 0ドル) }
 }
 .sorted{ 0ドル.position < 1ドル.position }
 .map{ 0ドル.element }
 case .first, .last:
 var unspecifiedItems = Array<Element>() //items whose ordering isn't in the sortingOrder
 let sortedPortion = self.flatMap { (element: Element) -> (element: Element, position: Int)? in
 let sortingMember = sortingMemberDeriver(element)
 guard let position = sortingOrder.index(of: sortingMember) else {
 unspecifiedItems.append(element)
 return nil
 }
 return (element: element, position: position)
 }
 .sorted{ 0ドル.position < 1ドル.position }
 .map{ 0ドル.element }
 switch unspecifiedItemSortingPolicy {
 case .first: return unspecifiedItems + sortedPortion
 case .last: return sortedPortion + unspecifiedItems
 default: fatalError("This should never happen.")
 }
 }
 }
}
extension MutableCollection where Iterator.Element: Equatable {
 func sorted(
 byOrderIn sortingOrder: [Element],
 sortUnspecifiedItems unspecifiedItemSortingPolicy: UnspecifiedItemSortingPolicy = .assertAllItemsHaveDefinedSorting
 ) -> [Element] {
 return self.sorted(byOrderOf: {0ドル}, in: sortingOrder, sortUnspecifiedItems: unspecifiedItemSortingPolicy)
 }
}

From there, the usage is really easy and elegant:

struct Pet {
 let name: String
}
let pets = [Pet(name: "Z"), Pet(name: "F"), Pet(name: "A"), Pet(name: "E")]
let petNames = ["E", "F", "Z", "A"]
let sorted = pets.sorted(byOrderOf: { 0ドル.name }, in: petNames, sortUnspecifiedItems: .last)
sorted.forEach{ print(0ドル) }