'Extending Array to check if it is sorted in Swift?
I want to extend Array class so that it can know whether it is sorted (ascending) or not. I want to add a computed property called isSorted. How can I state the elements of the Array to be comparable?
My current implementation in 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
The error Could not find an overload for '>' that accepts the supplied arguments
Of course, I still got an error because Swift doesn't know how to compare the elements. How can I implement this extension in Swift? Or am I doing something wrong here?
Solution 1:[1]
The alternative solution to a free function is to do what Swift's built-in Array.sort and Array.sorted methods do, and require that you pass a suitable comparator to the method:
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
Solution 2:[2]
In Swift 2.0 you can now extend protocols!
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
Note that because we're using Indexable.Index instead of a simple Int as an index we have to use a while-loop instead, which looks a bit less pretty and clear.
Solution 3:[3]
In Swift 4.2 and later you can cobble together allSatisfy and zip with some sequence slicing:
extension Array where Element: Comparable {
func isAscending() -> Bool {
return zip(self, self.dropFirst()).allSatisfy(<=)
}
func isDescending() -> Bool {
return zip(self, self.dropFirst()).allSatisfy(>=)
}
}
Solution 4:[4]
Actually, you can extend the Sequence protocol for a more generic solution:
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: <)
}
}
Solution 5:[5]
You've hit a problem with Swift's generics that can't be solved the way you like it right now (maybe in a future Swift version). See also Swift Generics issue.
Currently, you'll need to define a function (for example at the global scope):
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
The error message is misleading, IMHO, as the actual error is something like "UIView doesn't satisfy the type constraint Comparable".
Solution 6:[6]
Adaptation, a solution that will work in 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
}
}
Solution 7:[7]
The most flexible solution to me is a combination of NSAddict's and Wes Campaigne's answer. I.e. combine the advantage of being able to extend protocols and to pass comparator functions as arguments. This eliminates the restrictions both to use it only with arrays and to constrain it to elements conforming to Comparable protocol.
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
}
}
This can be used on any Collection type and sorting criteria can be defined according to your needs.
Solution 8:[8]
Here is a solution in Swift 4 that won't crash when self.count is equal or less than 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
}
}
This snippet supposes that an array of 1 or 0 elements is already sorted.
The reason to start with 1 in the for-loop range is: In case self.count <= 1, the loop will be skipped, a small performance increase. Using stride instead of ..< avoids the crash when the upper bound is < than the lower bound of a range.
Here are some examples:
[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
Solution 9:[9]
If you want simple function without arguments, like sort() or sorted() in 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
}
}
Solution 10:[10]
The generic function, zip(), can provide a shortcut for implementation.
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
Solution 11:[11]
@kAzec's answer seems to not working when elements are equal. This is because areInIncreasingOrder(a, a) must be false according to the documentation.
The following should work fine.
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: <)
}
}
Solution 12:[12]
Summarising previous answers there is a smallest universal Array extension to check:
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
Solution 13:[13]
Other answers have incorporated allSatisfy, but not adjacentPairs, which makes this so easy that this extension may not be warranted.
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)
However, it's very common to want to use a property of the elements for this, not the elements themselves:
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, >))
Solution 14:[14]
Just for fun. This supports duplicated elements that are equal as well:
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
}
}
}
Usage:
[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
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow