Расширение массива, чтобы проверить, отсортировано ли оно в Swift?

Ответ 1

Альтернативным решением для бесплатной функции является выполнение того, что делают встроенные методы Array.sort и Array.sorted Swift, и требуют, чтобы вы передали подходящий компаратор методу:

extension Array {
    func isSorted(isOrderedBefore: (T, T) -> Bool) -> Bool {
        for i in 1..<self.count {
            if !isOrderedBefore(self[i-1], self[i]) {
                return false
            }
        }
        return true
    }
}

[1, 5, 3].isSorted(<) // false
[1, 5, 10].isSorted(<) // true
[3.5, 2.1, -5.4].isSorted(>) // true

Ответ 2

В Swift 2.0 теперь вы можете расширять протоколы!

extension CollectionType where Generator.Element: Comparable {

    public var isSorted: Bool {

        var previousIndex = startIndex
        var currentIndex = startIndex.successor()

        while currentIndex != endIndex {

            if self[previousIndex] > self[currentIndex] {
                return false
            }

            previousIndex = currentIndex
            currentIndex = currentIndex.successor()
        }

        return true
    }

}

[1, 2, 3, 4].isSorted // true
["a", "b", "c", "e"].isSorted // true
["b", "a", "c", "e"].isSorted // false
[/* Anything not implementing `Comparable` */].isSorted // <~~ Type-error

Обратите внимание, что, поскольку мы используем Indexable.Index вместо простого Int в качестве индекса, мы должны использовать while-loop вместо этого, который выглядит немного менее красивым и понятным.

Ответ 3

Вы столкнулись с проблемой с генериками Swift, которые не могут быть решены так, как вам нравится прямо сейчас (возможно, в будущей версии Swift). См. Также Проблема Swift Generics.

В настоящее время вам необходимо определить функцию (например, в глобальной области):

func isSorted<T: Comparable>(array: Array<T>) -> Bool {
    for i in 1..<array.count {
        if array[i-1] > array[i] {
            return false
        }
    }

    return true
}

let i = [1, 2, 3]
let j = [2, 1, 3]
let k = [UIView(), UIView()]
println(isSorted(i)) // Prints "true"
println(isSorted(j)) // Prints "false"
println(isSorted(k)) // Error: Missing argument for parameter #2 in call

Сообщение об ошибке вводит в заблуждение, ИМХО, поскольку фактическая ошибка - это что-то вроде "UIView не удовлетворяет типу ограничений Comparable".

Ответ 4

На самом деле, вы можете расширить протокол Sequence для более общего решения:

extension Sequence {
    func isSorted(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Bool {
        var iterator = makeIterator()

        guard var previous = iterator.next() else {
            // Sequence is empty
            return true
        }

        while let current = iterator.next() {
            guard try areInIncreasingOrder(previous, current) else {
                return false
            }

            previous = current
        }

        return true
    }
}

extension Sequence where Element : Comparable {
    func isSorted() -> Bool {
        return isSorted(by: <)
    }
}

Ответ 5

Адаптация, решение, которое будет работать в Swift 4

extension Array where Iterator.Element: Comparable {
    func isSorted(isOrderedBefore: (Iterator.Element, Iterator.Element) -> Bool) -> Bool  {
        for i in 1 ..< self.count {
            if isOrderedBefore(self[i], self[i-1]) {
                return false
            }
        }
        return true
    }
}

Ответ 6

Наиболее гибким решением для меня является сочетание ответа NSAddict и Wes Campaigne. То есть объединить преимущество возможности расширять протоколы и передавать функции компаратора в качестве аргументов. Это устраняет ограничения как для использования только с массивами, так и для ограничения его на элементы, соответствующие протоколу Comparable.

extension CollectionType
{
    func isSorted(isOrderedBefore: (Generator.Element, Generator.Element) -> Bool) -> Bool
    {
        var previousIndex = startIndex
        var currentIndex = startIndex.successor()

        while currentIndex != endIndex
        {
            if isOrderedBefore(self[previousIndex], self[currentIndex]) == false
            {
                return false
            }

            previousIndex = currentIndex
            currentIndex = currentIndex.successor()
        }

        return true
    }
}

Это может использоваться для любого типа Collection, и критерии сортировки могут быть определены в соответствии с вашими потребностями.

Ответ 7

Общая функция, zip(), может предоставить ярлык для реализации.

extension Collection where Element: Comparable {
    var isSorted: Bool {
        guard count > 1 else {
            return true 
        }

        let pairs = zip(prefix(count - 1), suffix(count - 1))

        return !pairs.contains { previous, next in
            previous > next
        }
    }
}

[0, 1, 1, 2].isSorted  // true
[0, 2, 2, 1].isSorted  // false

Ответ 8

Вот решение в Swift 4, которое не будет аварийно self.count если self.count равно или меньше 1:

extension Array where Element: Comparable {
    func isSorted(by isOrderedBefore: (Element, Element) -> Bool) -> Bool {
        for i in stride(from: 1, to: self.count, by: 1) {
            if !isOrderedBefore(self[i-1], self[i]) {
                return false
            }
        }
        return true
    }
}

Этот фрагмент предполагает, что массив из 1 или 0 элементов уже отсортирован.

Причина для начала с 1 в диапазоне цикла for: в случае self.count <= 1 цикл будет пропущен, что приведет к небольшому увеличению производительности. Использование stride вместо ..< позволяет избежать сбоя, когда верхняя граница <ниже нижней границы диапазона.

Вот некоторые примеры:

[1, 2, 3].isSorted(by: >) // true
[3, 2, 2].isSorted(by: >=) // true
[1, 4, 7].isSorted(by: {x, y in
    return x + 2 < y * y
}) // true

let a: [Int] = [1]
a.isSorted(by: <) // true


let b: [Int] = []
b.isSorted(by: >) // true

Ответ 9

Если вам нужна простая функция без аргументов, такая как sort() или sorted() в Swift:

extension Array where Element : Comparable {
    func isSorted() -> Bool {
        guard self.count > 1 else {
            return true
        }

        for i in 1..<self.count {
            if self[i-1] > self[i] {
                return false
            }
        }
        return true
    }
}

Ответ 10

В Swift 4.2 и более поздних версиях вы можете объединить allSatisfy и zip с помощью некоторого среза последовательности:

extension Array where Element: Comparable{
    func isAscending() -> Bool {
        return zip(self, self.dropFirst()).allSatisfy(<=)
    }

    func isDescending() -> Bool {
        return zip(self, self.dropFirst()).allSatisfy(>=)
    }
}