Как вставить элемент в правильное положение в отсортированный массив в Swift?

Ответ 1

Вот возможная реализация в Swift с использованием двоичного поиска (из http://rosettacode.org/wiki/Binary_search#Swift с небольшими изменениями):

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
    }
}

Как и в случае indexOfObject:inSortedRange:options:usingComparator:, предполагается, что массив сортируется относительно компаратора. Он возвращает либо (любой) индекс элемента, если элемент уже присутствует в массив или индекс, где он может быть вставлен при сохранении порядка. Эта соответствует NSBinarySearchingInsertionIndex метода NSArray.

Использование:

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

Ответ 2

В swift 3 вы можете использовать index(where:):

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

Обратите внимание, что в этом случае вам нужно отменить условие внутри замыкания (т.е. > вместо < для увеличения элементов в массиве), потому что интересующий вас индекс - это первый элемент, который НЕ соответствует сказуемое. Кроме того, этот метод вернет nil, если вновь вставленный элемент будет последним в массиве (newElement = "z" в приведенном выше примере.

Для удобства это можно обернуть в отдельную функцию, которая будет обрабатывать все эти проблемы:

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
    }
}

Использование:

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

Ответ 3

Если вы знаете, что ваш массив отсортирован, вы можете использовать этот метод - он будет работать с массивами любого типа. Он будет перемещаться по всему массиву каждый раз, поэтому не используйте его с большими массивами - перейдите к другому типу данных, если у вас есть большие потребности!

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]

Ответ 4

Двоичное дерево поиска здесь - путь.

В упорядоченном массиве возьмите элемент посередине и посмотрите, больше ли объект в этой позиции, чем ваш новый объект. Таким образом, вы можете забыть половину элементов массива с помощью одного сравнения.

Повторите этот шаг с оставшейся половиной. Опять же, при одном сравнении вы можете забыть половину оставшихся объектов. Количество ваших целевых элементов теперь составляет четверть от размера массива в начале с двумя сравнениями.

Повторите это, пока не найдете правильную позицию для вставки нового элемента.

Вот хорошая статья о двоичных деревьях поиска с быстрым

Ответ 5

В соответствии с сеансом 406 2018 г. WWDC: "Быстрая обобщенность" (расширенный) бинарный поиск может быть выполнен более эффективным и даже более общим способом, разрезая объект коллекции.

Есть два существенных преимущества Slice:

1. Срез всегда является подмножеством исходного объекта без выделения дополнительной памяти.
2. Все индексы среза относятся к исходному объекту.
   Например, если вы нарезаете массив из 5 объектов, то let slice = array[2..<4] тогда slice.startIndex равен 2 не 0.

RandomAccessCollection - это протокол (унаследованный от BidirectionalCollection), которому соответствуют различные структуры/классы

extension RandomAccessCollection where Element : Comparable {
    func insertionIndex(of value: Element) -> Index {
        var slice : SubSequence = self[...]

        while !slice.isEmpty {
            let middle = slice.index(slice.startIndex, offsetBy: slice.count / 2)
            if value < slice[middle] {
                slice = slice[..<middle]
            } else {
                slice = slice[index(after: middle)...]
            }
        }
        return slice.startIndex
    }
}

Пример:

let array = [1, 2, 4, 7, 8]
let index = array.insertionIndex(of: 6) // 3

Вы можете расширить функцию для проверки на предикатное закрытие вместо одного значения

extension RandomAccessCollection { // the predicate version is not required to conform to Comparable
    func insertionIndex(for predicate: (Element) -> Bool) -> Index {
        var slice : SubSequence = self[...]

        while !slice.isEmpty {
            let middle = slice.index(slice.startIndex, offsetBy: slice.count / 2)
            if predicate(slice[middle]) {
                slice = slice[index(after: middle)...]
            } else {
                slice = slice[..<middle]
            }
        }
        return slice.startIndex
    }
}

Пример:

struct Person { let name : String }

let array = [Person(name: "Adam"), Person(name: "Cynthia"), Person(name: "Nancy"), Person(name: "Tom")]
let index = array.insertionIndex{ $0.name < "Bruce" } // 1