[SOLVED] How do I insert an element at the correct position into a sorted array in Swift?

Issue

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)

Solution

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, at: index)

Answered By – Martin R

Answer Checked By – Terry (BugsFixing Volunteer)

Leave a Reply

Your email address will not be published.