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?

possible duplicate of How to implement flatten as an extension on an Array without type casting? — Sebastian
– Sebastian, Commented Jul 7, 2014 at 3:31
You can't extend Array<Comparable>, but you can implement a function that operates on Array<Comparable>. Have a look at stackoverflow.com/a/24565627/1489997 — Sebastian
– Sebastian, Commented Jul 7, 2014 at 3:37
@Sebastian I think the link that you gave is quite different than my intention. It's pretty easy to make category for this kind of thing in obj-c, so I thought it should be as trivial in Swift. — Ikhsan Assaat
– Ikhsan Assaat, Commented Jul 7, 2014 at 13:45
@IkhsanAssaat this is not any easier in Objective C. You still have to find a way to compare elements, and ObjC doesn't give you a magical function to do that. I suggest you try writing such a function in Objective C, then maybe you'll understand why. — Kevin
– Kevin, Commented Jul 13, 2014 at 17:31
@Kevin: The problem is easier in Objective-C since an NSArray can only store objects, and you can ask them whether they implement a protocol or respond to a selector (compare:). Also, you can force casting in Objective-C. With Swift, the problem is harder as Swift doesn't allow you to "work around" the compiler. Also, there are @objc protocols and non-@objc protocols and you can only check whether a type conforms to the later, but Comparable is non-@objc. That's why let foo = (bar as Any) as? Comparable doesn't work: the compiler does not allow you to "trick" it. — DarkDust
– DarkDust, Commented Jul 13, 2014 at 17:54

Wes Campaigne · Accepted Answer · 2014-07-15 21:27:35Z

35

+50

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

answered Jul 15, 2014 at 21:27

Wes Campaigne

4,1803 gold badges24 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

nschum Over a year ago

Note that this actually fails for the example provided in the question: [1, 1, 2, 3, 4, 5, 6, 7, 8].isSorted(<), because it doesn't handle repeated values.

AmigoNico Over a year ago

I think you want to change if !isOrderedBefore(self[i-1], self[i]) to if isOrderedBefore(self[i], self[i-1]) to fix the problem pointed out by nschum.

juancazalla Over a year ago

Be careful, this solution would crash with empty arrays. I would add a guard checking that it isn't an empty array

Palimondo · Accepted Answer · 2019-12-04 07:29:57Z

23

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

edited Dec 4, 2019 at 7:29

answered Apr 29, 2019 at 18:24

Palimondo

7,3914 gold badges43 silver badges59 bronze badges

Comments

IluTov · Accepted Answer · 2016-03-05 10:22:21Z

20

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.

edited Mar 5, 2016 at 10:22

answered Jun 15, 2015 at 16:27

IluTov

6,8486 gold badges44 silver badges108 bronze badges

1 Comment

markedwardmurray Over a year ago

And for Swift 3, Generator becomes Iterator and someIndex.successor() becomes self.index(after: someIndex)

kAzec · Accepted Answer · 2018-08-05 15:30:40Z

7

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

answered Aug 5, 2018 at 15:30

kAzec

711 silver badge2 bronze badges

1 Comment

Alexander Over a year ago

Everything you did here to make an iterator, get its next elements, conditionally unwrap them and loop, is actually exactly what for does. This could just be for current in self { ... }

score 4 · Accepted Answer · 2023-02-06 18:09:48Z

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

adnv · Accepted Answer · 2018-03-18 12:17:45Z

2

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

answered Mar 18, 2018 at 12:17

adnv

1012 silver badges6 bronze badges

Comments

RTasche · Accepted Answer · 2016-09-09 10:49:30Z

1

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.

answered Sep 9, 2016 at 10:49

RTasche

2,6541 gold badge18 silver badges20 bronze badges

1 Comment

markedwardmurray Over a year ago

And for Swift 3 replace someIndex.successor() with self.index(after: someIndex)

ielyamani · Accepted Answer · 2018-08-05 17:24:10Z

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

iUrii · Accepted Answer · 2021-04-12 10:06:29Z

1

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

answered Apr 12, 2021 at 10:06

iUrii

14.4k2 gold badges41 silver badges65 bronze badges

Comments

Ivo Leko · Accepted Answer · 2018-10-31 10:45:19Z

0

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

edited Oct 31, 2018 at 10:45

answered Oct 31, 2018 at 8:31

Ivo Leko

8201 gold badge12 silver badges21 bronze badges

Comments

otto · Accepted Answer · 2019-04-17 19:27:57Z

0

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

edited Apr 17, 2019 at 19:27

answered Nov 29, 2018 at 22:10

otto

2,2603 gold badges26 silver badges26 bronze badges

Comments

Barış Deniz Sağlam · Accepted Answer · 2020-08-10 16:01:48Z

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

Leo Dabus · Accepted Answer · 2022-04-17 03:09:54Z

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

Collectives™ on Stack Overflow

Extending Array to check if it is sorted in Swift?

13 Answers 13

3 Comments

Comments

1 Comment

1 Comment

Comments

Comments

1 Comment

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

13 Answers 13

3 Comments

Comments

1 Comment

1 Comment

Comments

Comments

1 Comment

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related