Reorder array compared to another array in Swift

Question

I have one array in Swift containing some ids of objects, and I have another array containing these objects with their ids, so something like this:

class MyObject {
   let id: String
   ...
}

let ids: [String] = ...
let objects: [MyObject] = ...

Now the array of ids is sorted in some custom order, and I need the array of objects to be sorted in the same order. So for example:

let ids: [String] = ["1", "2", "3"]
let objects: [MyObject] = [obj3, obj1, obj2]
// obj1.id = "1"
// obj2.id = "2"
// obj3.id = "3"
objects.reorder(template: ids) 
// Now objects = [obj1, obj2, obj3]

So I basically need to implement this reorder method. Does anyone have a smart suggestion how to do this in Swift? I'm using Swift 3, so all the new APIs are available to me.

Answer 1

You can sort objects in order to follow the order in ids writing

let sorted = objects.sort { ids.indexOf($0.id) < ids.indexOf($1.id) }
// [{id "1"}, {id "2"}, {id "3"}]

Another example

let ids: [String] = ["3", "2", "1"]
let objects: [MyObject] = [MyObject(id: "3"), MyObject(id: "1"), MyObject(id: "2")]

let sorted = objects.sort { ids.indexOf($0.id) < ids.indexOf($1.id) }
// [{id "3"}, {id "2"}, {id "1"}]

This code is in Swift 2.2

---

Swift 4.2 solution

let sorted = objects.sorted { ids.index(of: $0.id)! < ids.index(of: $1.id)! }

Answer 2

A possible solution:

let sorted = objects.flatMap { obj in
    ids.index(of: obj.id).map { idx in (obj, idx) }
}.sorted(by: { $0.1 < $1.1 } ).map { $0.0 }

Explanation:

• First, each object is tied to together with the corresponding position of the id in the array, this gives an array of (object, index) tuples.
• This array is sorted with respect to the index positions.
• Finally, the objects are extracted again.

Possible advantages:

• Each object is searched only once in the array.
• Objects for which no id exists in the array are ignored.

Answer 3

I am not a computer science person, but it seems to me that this business of repeatedly calling indexOf is wasteful. Surely the right approach would be to walk through the template array (ids in this case) once in advance, building a dictionary that associates each element with its position in the array:

let ids = ["1", "2", "3"]
var d = [String:Int]()
for (ix,id) in ids.enumerated() {
    d[id] = ix
}

Now we've got a dictionary, and lookup in a dictionary is fast. So we can use each object's id as the key and sort on the corresponding value. Let's say that this is our initial array of objects:

class MyObject {
    let id: String
    init(id:String) {self.id = id}
}
let objects = [MyObject(id:"3"), MyObject(id:"1"), MyObject(id:"2")]

Now sorting is a one-liner:

let objectsSorted = objects.sorted { d[$0.id]! < d[$1.id]! }

The advantage here is especially obvious if you know you're going to be using ids as a template often, because you only have to form the dictionary d once and now you're ready to sort against that template as many times as you like. In effect, the dictionary memoizes the sort order. (Granted, I have not taken into account what happens if the dictionary lookup were to fail; we just crash.)

---

We can generalize that approach, based on the fact that in order to serve as a dictionary key, the values in the template array must be hashable:

struct Cosorter<K:Hashable> {
    let d : [K:Int]
    init(_ arr:[K]) {
        var dd = [K:Int]()
        for (ix,val) in arr.enumerated() {
            dd[val] = ix
        }
        self.d = dd
    }
    func lt(_ v1:K, _ v2:K) -> Bool {
        return self.d[v1]! < self.d[v2]!
    }
}

Now each template is transformed into a Cosorter instance initialized with the template array, thus causing the dictionary to be prepared, once:

let idsTemplate = Cosorter(ids)

Any time we want to cosort on that template, we just use that template's lt as the ordering function:

let objectsSorted = objects.sorted {idsTemplate.lt($0.id,$1.id)}

Answer 4

Be aware that the reorder method fails if the id could not be found in unsorted

func reorder(items: [MyObject], order : [String]) -> [String] {
    var unsorted = items
    var ordered : [String] = []
    for orderId in order {
        let index = unsorted.filter{ $0.id == orderId }.first
        let found = unsorted.remove(at: index!)
        ordered.append(found)
    }
    return ordered
}