How do I insert an element at the correct position

Question

NSArray has - (NSUInteger)indexOfObject:(id)obj inSortedRange:(NSRange)r options:(NSBinarySearchingOptions)opts usingComparator:(NSComparator)cmp to determine the insert position of a new object in a sorted array.

What is the best and high-performance way to do this in pure Swift?

Something along the lines of:

var myArray = ["b", "e", "d", "a"]
myArray.sort { $0 < $1 }

// myArray is now [a, b, d, e]

myArray.append("c")
myArray.sort { $0 < $1 }

// myArray is now [a, b, c, d, e]

Instead of appending the new element and then sorting the array, I would like to figure out the correct position and insert the element:

let index = [... how to calculate this index ??? ...]
myArray.insert("c", atIndex: index)

Answer 1

Here is a possible implementation in Swift using binary search (from http://rosettacode.org/wiki/Binary_search#Swift with slight modifications):

extension Array {
    func insertionIndexOf(elem: Element, isOrderedBefore: (Element, Element) -> Bool) -> Int {
        var lo = 0
        var hi = self.count - 1
        while lo <= hi {
            let mid = (lo + hi)/2
            if isOrderedBefore(self[mid], elem) {
                lo = mid + 1
            } else if isOrderedBefore(elem, self[mid]) {
                hi = mid - 1
            } else {
                return mid // found at position mid
            }
        }
        return lo // not found, would be inserted at position lo
    }
}

As with indexOfObject:inSortedRange:options:usingComparator: it is assumed that the array is sorted with respect to the comparator. It returns either (any) index of the element if the element is already present in the array, or the index where it can be inserted while preserving the order. This corresponds to the NSBinarySearchingInsertionIndex of the NSArray method.

Usage:

let newElement = "c"
let index = myArray.insertionIndexOf(newElement) { $0 < $1 } // Or: myArray.indexOf(c, <)
myArray.insert(newElement, atIndex: index)

Answer 2

A binary search tree here is the way to go.

On an ordered array, take the element in the middle and see if the object at that position is greater than your new object. That way you can forget the half of the array elements with one single comparison.

Repeat that step with the remaining half. Again, with a single comparison you can forget the half of the remaining objects. Your target element count is now a quarter of the array size at the beginning with only two comparisons.

Repeat that until you found the correct position to insert the new element.

Here is a a good article on binary search trees with swift

Answer 3

If you know your array is sorted, you can use this method -- it will work with arrays of any type. It will traverse the whole array each time, so don't use this with large arrays - go for another data type if you have larger needs!

func insertSorted<T: Comparable>(inout seq: [T], newItem item: T) {
    let index = seq.reduce(0) { $1 < item ? $0 + 1 : $0 }
    seq.insert(item, atIndex: index)
}

var arr = [2, 4, 6, 8]
insertSorted(&arr, newItem: 5)
insertSorted(&arr, newItem: 3)
insertSorted(&arr, newItem: -3)
insertSorted(&arr, newItem: 11)
// [-3, 2, 3, 4, 5, 6, 8, 11]

Answer 4

In swift 3 you can use index(where:):

var myArray = ["a", "b", "d", "e"]
let newElement = "c"
if let index = myArray.index(where: { $0 > newElement }) {
    myArray.insert(newElement, at: index)
}

Note that in this case you need to reverse the condition inside the closure (i.e. > instead of < for increasing elements in array), because the index you are interested in is the first element that does NOT match the predicate. Also, this method will return nil if the newly inserted element is going to be the last in the array (newElement = "z" in the example above.

For convenience, this can be wrapped to a separate function that will handle all these issues:

extension Collection {
    func insertionIndex(of element: Self.Iterator.Element,
                        using areInIncreasingOrder: (Self.Iterator.Element, Self.Iterator.Element) -> Bool) -> Index {
        return index(where: { !areInIncreasingOrder($0, element) }) ?? endIndex
    }
}

Usage:

var myArray = ["a", "b", "d", "e"]
let newElement = "c"
let index = myArray.insertionIndex(of: newElement, using: <)
myArray.insert(newElement, at: index)