CODEWITHSUNDEEP
listclojuresorting
marius
marius

Reputation: 1613

How to verify if a list is sorted?

How can I, in Clojure, verify is a list of numbers is sorted?

(def my-list (list 1 2 3 1 4 2 2 4))

sorted? only returns true if the collection implements the sorted interface. I was looking for a reduce operation that would iterate the list pairwise, such as (reduce < my-list). I understand I could manually create pairs and compare these:

(letfn [(pair [l] (if (= (count l) 2) (list l) (cons (take 2 l) (pair (rest l)))))]
    (every? #(apply < %) (pair my-list)))

But that seems unnecessarily complex. It really seems to me as if I'm missing a basic function.

Upvotes: 9

Views: 1672

Answers (3)

noisesmith
noisesmith

Reputation: 20194

The simplest solution:

(apply <= mylist)

>= also works for reverse sorting

Upvotes: 26

Arthur Ulfeldt
Arthur Ulfeldt

Reputation: 91597

I would do a single pass over overlapping pairs of numbers and check they are <= (as you mention) because it is O(n), though you don't need to manually make pairs.

user> (partition-all 2 1 [1 2 3 4 5 6])
((1 2) (2 3) (3 4) (4 5) (5 6) (6))

user> (every? #(apply <= %) (partition-all 2 1 [1 2 3 4 6 5]))
false

user> (every? #(apply <= %) (partition-all 2 1 [1 2 3 4 5 6]))
true

Upvotes: 5

Tom Smilack
Tom Smilack

Reputation: 2075

You could sort the list and compare it to the original:

(= my-list (sort my-list))

Example:

> (def my-list (list 1 2 3 1 4 2 2 4))
#'sandbox3825/my-list

> (= my-list (sort my-list))
false

> (def my-list (list 1 2 3 4))
#'sandbox3825/my-list

> (= my-list (sort my-list))
true

Upvotes: 1

Related Questions