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

by

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)

More Related Contents:

  1. Swift how to sort array of custom objects by property value
  2. How to sort an array of custom objects by property value in Swift
  3. Sort Objects in Array by date
  4. Sorting a Swift array by ordering from another array
  5. How do I sort a swift array containing instances of NSManagedObject subclass by an attribute value (date)
  6. Swift sort an array with strings and numbers [duplicate]
  7. Generic function to sort array of class or struct by properties in Swift
  8. How to stable sort an array in swift?
  9. In Swift how can I sort one array based on another array?
  10. Algorithm for all subsets of Array
  11. How do I shuffle an array in Swift?
  12. Get random elements from array in Swift
  13. Why isn’t [SomeStruct] convertible to [Any]?
  14. How can I extend typed Arrays in Swift?
  15. Sorting a multidimensionnal array in VBA
  16. Finding sum of elements in Swift array
  17. How do I make a exact duplicate copy of an array?
  18. Adding items to Swift array across multiple threads causing issues (because arrays aren’t thread safe) – how do I get around that?
  19. Count the occurences a particular integer has in an array [duplicate]
  20. Find min / max value in Swift Array
  21. type any? has no subscript members
  22. Creating an extension to filter nils from an Array in Swift
  23. Compare arrays in swift
  24. In Swift, an efficient function that separates an array into 2 arrays based on a predicate
  25. Is there a way to instantly generate an array filled with a range of values in Swift?
  26. How can I decode a JSON response with an unknown key in Swift?
  27. How to merge two arrays in Swift
  28. How to forward functions with variadic parameters?
  29. Excel VBA Quickest way to sort an array of numbers in descending order?
  30. Swift: Binary search for standard array?

Leave a Comment