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

Question

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

Я хочу расширить класс Array, чтобы он мог знать, отсортирован ли он (по возрастанию) или нет. Я хочу добавить вычисляемое свойство с именем isSorted, Как я могу заявить, что элементы массива сопоставимы?

Моя текущая реализация в Playground

extension Array {
  var isSorted: Bool {
    for i in 1..self.count {
      if self[i-1] > self[i] { return false }
    }
    return true
  }
}

// The way I want to get the computed property
[1, 1, 2, 3, 4, 5, 6, 7, 8].isSorted //= true
[2, 1, 3, 8, 5, 6, 7, 4, 8].isSorted //= false

Ошибка Could not find an overload for '>' that accepts the supplied arguments

Конечно, я все еще получил ошибку, потому что Свифт не знает, как сравнивать элементы. Как я могу реализовать это расширение в Swift? Или я что-то здесь не так делаю?

30

arrays swift

Источник

user851515 07 июл '14 в 03:17

14 ответов

Решение

В 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(>=)
    }
}

23

Источник

user41307 29 апр '19 в 18:24

В 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, который выглядит немного менее симпатичным и понятным.

21

Источник

user1320374 15 июн '15 в 16:27

Вы столкнулись с проблемой дженериков 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".

7

Источник

user400056 13 июл '14 в 17:07

На самом деле, вы можете продлить 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: <)
    }
}

7

Источник

user6680298 05 авг '18 в 15:30

Адаптация, решение, которое будет работать в 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
    }
}

3

Источник

user5316459 18 мар '18 в 12:17

Другие ответы включеныallSatisfy, но нетadjacentPairs, что делает это настолько простым, что это расширение может быть неоправданным.

      import Algorithms

public extension Sequence where Element: Comparable {
  /// Whether the elements of the sequence are in order.
  @inlinable var isSorted: Bool { adjacentPairs().allSatisfy(<) }
}

      let random = Int.random(in: 1...(.max))
let stride = stride(from: -random, through: random, by: random)
XCTAssert(stride.isSorted)
XCTAssertFalse(stride.reversed().isSorted)

Однако очень часто для этого хотят использовать свойство элементов, а не сами элементы:

      import Algorithms

public extension Sequence {
  /// Whether the elements of this sequence are sorted by a common `Comparable` value.
  @inlinable func isSorted<Comparable: Swift.Comparable>(
    by comparable: (Element) throws -> Comparable
  ) rethrows -> Bool {
    try isSorted(by: comparable, <)
  }

  /// Whether the elements of this sequence are sorted by a common `Comparable` value,
  /// and sorting closure.
  @inlinable func isSorted<Comparable: Swift.Comparable>(
    by comparable: (Element) throws -> Comparable,
    _ areInIncreasingOrder: (Comparable, Comparable) throws -> Bool
  ) rethrows -> Bool {
    try adjacentPairs().allSatisfy {
      try areInIncreasingOrder(comparable($0), comparable($1))
    }
  }
}

      struct TypeWithComparable {
  let comparable: Int
}

let random = Int.random(in: 1...(.max))
let stride =
  stride(from: -random, through: random, by: random)
    .lazy.map(TypeWithComparable.init)
XCTAssert(stride.isSorted(by: \.comparable))
XCTAssert(stride.reversed().isSorted(by: \.comparable, >))

3

Источник

user652038 07 апр '22 в 19:46

Вот решение в Swift 4, которое не будет зависать при 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

1

Источник

user2907715 05 авг '18 в 17:24

Подводя итог предыдущим ответам, можно проверить наименьшее универсальное расширение массива:

      extension Array {
    func isSorted(_ predicate: (Element, Element) throws -> Bool) -> Bool {
        guard count > 1 else { return true }
        return (try? zip(self, self.dropFirst()).allSatisfy(predicate)) == true
    }
}

// Standard types

[1, 2, 3, 4, 5].isSorted(<) // true
[1, 2, 10, 4, 5].isSorted(<) // false

[10, 5, 4, 3, 1].isSorted(>) // true
[10, 20, 4, 3, 1].isSorted(>) // false


// Custom types

struct MyStruct {
    let i: Int
}

let items = [MyStruct(i: 1), MyStruct(i: 2), MyStruct(i: 3), MyStruct(i: 10)]
let sorted = items.isSorted { $0.i < $1.i } // true

1

Источник

user979986 12 апр '21 в 13:06

Если вам нужна простая функция без аргументов, например 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
    }
}

1

Источник

user774394 31 окт '18 в 08:31

Универсальная функция, 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

1

Источник

user148076 29 ноя '18 в 22:10

Самое гибкое решение для меня - это сочетание ответа 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 Тип и критерии сортировки могут быть определены в соответствии с вашими потребностями.

1

Источник

user1757581 09 сен '16 в 10:49

Просто для удовольствия. Это поддерживает дублированные элементы, которые также равны:

      extension Sequence {
    var neighbors: Zip2Sequence<Self, DropFirstSequence<Self>> {
        zip(self, dropFirst())
    }
    func isSorted<T: Comparable>(_ predicate: (Element) throws -> T) rethrows -> Bool {
        try isSorted(predicate, by: <)
    }
    func isSorted<T: Comparable>(
        _ predicate: (Element) throws -> T,
        by areInIncreasingOrder: (T, T) throws -> Bool
    ) rethrows -> Bool {
        try neighbors.allSatisfy {
            try areInIncreasingOrder(predicate($0), predicate($1)) ||
            predicate($0) == predicate($1)
        }
    }
}

      extension Sequence where Element: Comparable {
    var isSorted: Bool { isSorted(by: <) }
    func isSorted(
        by areInIncreasingOrder: (Element, Element) throws -> Bool
    ) rethrows -> Bool {
        try neighbors.allSatisfy {
            try areInIncreasingOrder($0, $1) || $0 == $1
        }
    }
}

Применение:

      [1,2,2,3].isSorted         // true
[3,2,2,1].isSorted(by: >)  // true

      struct Test {
    let id: Int
}

[1,2,2,3].map(Test.init).isSorted(\.id)          // true
[3,2,2,1].map(Test.init).isSorted(\.id, by: >)   // true

0

Источник

user2303865 17 апр '22 в 03:03

Ответ @kAzec, похоже, не работает, когда элементы равны. Это связано с тем, что areIncreasingOrder(a, a) должно быть false согласно документации.

Следующее должно работать нормально.

extension Sequence {
    func isSorted(by areInIncreasingOrder: (Element, Element) throws -> Bool)
        rethrows -> Bool {
        var it = makeIterator()
        guard var previous = it.next() else { return true }
        
        while let current = it.next() {
            if try !areInIncreasingOrder(previous, current) &&
                areInIncreasingOrder(current, previous) {
                return false
            }
            previous = current
        }
        return true
    }
}

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

0

Источник

user6641096 10 авг '20 в 19:01

Другие вопросы по тегам arrays swift

user719748 15 июл '14 в 21:27 2014-07-15 21:27 · Accepted Answer · 2014-07-15 21:27

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

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