This question already has answers here:
Closed 7 months ago.
I have one array that defines an order,
let orderSettingArray = ["Admiral", "Captain", "Lieutenant"]
and another array with a few of these values
var myArray = ["Lieutenant", "Captain"]
I want to sort myArray to reflect the order of orderSettingArray:
var myArraySorted = myArray.getSorted(by: orderSettingArray)
Now print(myArraySorted) should print ["Captain", "Lieutenant"]
Update
I've found a better design for this. It has quite a few improvements:
- I use a
Dictionary to speed up ordering look-ups
- By extracting this behaviour into a separate type, the dictionary can be cached and reused between multiple sorts
- The ordering-derivation is decoupled from sorting, so it could be used in more ways
- The
omitEntirely responsibility was removed entirely. It should instead by done by a simple call to filter, with hardcodedOrdering.contains as the predicate.
See my new answer, here
Old answer:
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:
let sortingOrder = ["Admiral", "Captain", "Lieutenant"]
let ranks = ["Lieutenant", "Captain"]
let sortedRanks = ranks.sorted(byOrderIn: sortingOrder)
print(sortedRanks)
Unlike most other solutions you'll see to this problem, this extension handles the cases where the array you're sorting contains items whose sort order is not defined in the sortingOrder array. There's a defaulted argument that lets you specify whether such items should come first (.first), last (.last), or be omitted entirely (.omitEntirely) from the result.
Additionally, this algorithm only performs one index(of:) call per element of the array being sorted, so performance is pretty decent even when sorting large arrays. However, this algorithm is O(sortingOrder.count). If there are a lot of elements in sortingOrder, then it might be worth refactoring this to take a dictionary, mapping elements to relatives integers that define the sort order.
So Easy let new = orderSettingArray.filter{ return myArray.contains($0) }
Map each array element to a (element, index) tuple, where
the index is the index of the array element in the order array.
In your example that would be
[("Lieutenant", 2), ("Captain", 1)]
Sort the array of tuples by the second tuple element (the index).
In your case
[("Captain", 1), ("Lieutenant", 2)]
Extract the array elements from the sorted tuples array.
In your case
["Captain", "Lieutenant"]
Code (for any array of equatable elements, not restricted to arrays of strings):
extension Array where Element: Equatable {
func getSorted(by orderArray: [Element]) -> [Element] {
return self.map { ($0, orderArray.index(of: $0) ?? Int.max) }
.sorted(by: { $0.1 < $1.1 })
.map { $0.0 }
}
}
let orderSettingArray = ["Admiral", "Captain", "Lieutenant"]
let myArray = ["Lieutenant", "Captain"]
let myArraySorted = myArray.getSorted(by: orderSettingArray)
print(myArraySorted) // ["Captain", "Lieutenant"]
Elements in myArray which are not present in orderSettingArray
are assigned the index Int.max and therefore sorted to the end
of the result.
Swift 3
extension Array where Element: Hashable {
func getSorted(by: Array<String>) -> Array<String> {
var d = Dictionary<Int, String>()
for value in self {
for i in 0 ..< by.count {
if value as! String == by[i] {
d[i] = value as? String
}
}
}
var sortedValues = Array<String>()
for key in d.keys.sorted(by: <) {
sortedValues.append(d[key]!)
}
return sortedValues
}
}
