Extending Array to check if it is sorted in Swift?

Question

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?

Answer 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

Answer 2

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

Answer 3

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.

Answer 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: <)
    }
}

Answer 5

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

Answer 6

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, >=))

Answer 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.

Answer 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

Answer 9

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

Answer 10

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

Answer 11

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

Answer 12

@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: <)
    }
}

Answer 13

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