Check to see if an array is already sorted?

Question

I know how to put an array in order, but in this case I just want to see if it is in order. An array of strings would be the easiest, I imagine, and answers on that front are appreciated, but an answer that includes the ability to check for order based on some arbitrary parameter is optimal.

Here's an example dataset. The name of:

[["a", 3],["b",53],["c",2]]

Where the elements are themselves arrays containing several elements, the first of which is a string. I want to see if the elements are in alphabetical order based on this string.

Solution 1

It looks like a generic abstraction, let's open Enumerable:

module Enumerable
  def sorted?
    each_cons(2).all? { |a, b| (a <=> b) <= 0 }
  end
end

[["a", 3], ["b", 53],["c", 2]].sorted? #=> true

Notice that we have to write (a <=> b) <= 0 instead of a <= b because there are classes that support <=> but not the comparator operators (i.e. Array), since they do not include the module Comparable.

You also said you'd like to have the ability "to check for order based on some arbitrary parameter":

module Enumerable  
  def sorted_by?
    each_cons(2).all? { |a, b| ((yield a) <=> (yield b)) <= 0 }    
  end
end

[["a", 3], ["b", 1], ["c", 2]].sorted_by? { |k, v| v } #=> false

Using lazy enumerables (Ruby >= 2.1), we can reuse Enumerable#sorted?:

module Enumerable  
  def sorted_by?(&block)
    lazy.map(&block).sorted?
  end
end

Solution 2

You can compare them two by two:

[["a", 3],["b",53],["c",2]].each_cons(2).all?{|p, n| (p <=> n) != 1} # => true

Solution 3

reduce can compare each element to the one before, and stop when it finds one out of order:

array.reduce{|prev,l| break unless l[0] >= prev[0]; l}

Solution 4

If it turns out the array isn't sorted, will your next action always be to sort it? For that use case (though of course depending on the number of times the array will already be sorted), you may not want to check whether it is sorted, but instead simply choose to always sort the array. Sorting an already sorted array is pretty efficient with many algorithms and merely checking whether an array is already sorted is not much less work, making checking + sorting more work than simply always sorting.

Solution 5

def ascending? (array)
    yes = true
    array.reduce { |l, r| break unless yes &= (l[0] <= r[0]); l }
    yes
end


def descending? (array)
    yes = true
    array.reduce { |l, r| break unless yes &= (l[0] >= r[0]); l }
    yes
end

View more solutions

Comments

[GlyphGryph]

Uh... no I didn't. I swapped out a generic example for a concrete example, that was all. Wanting to be able to compare on some arbitrary component of the array elements was a component of the original question.

[tibbon]

Doesn't work for me ``` [1, 2, 3].reduce{|prev,l| break unless l[0] >= prev[0]; l} => nil [3, 2, 1].reduce{|prev,l| break unless l[0] >= prev[0]; l} => nil ```