Проверьте, отсортирован ли массив?

Я знаю, как упорядочить массив, но в этом случае я просто хочу посмотреть, все ли в порядке. Я считаю, что массив строк будет самым легким, и ответы на этом фронте оценены, но ответ, который включает в себя возможность проверки порядка, основанного на некоторых произвольных параметрах, является оптимальным.

Вот пример набора данных. Имя:

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

Если элементы сами представляют собой массивы, содержащие несколько элементов, первая из которых является строкой. Я хочу видеть, находятся ли элементы в алфавитном порядке на основе этой строки.

Ответ 1

Это общая абстракция, откройте Enumerable:

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

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

Обратите внимание, что мы должны писать (a <=> b) <= 0 вместо a <= b, потому что существуют классы, поддерживающие <=>, но не операторы-компараторы (т.е. Array), поскольку они не включают модуль Comparable.

Вы также сказали, что хотите иметь возможность "проверять порядок на основе некоторых произвольных параметров":

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

С ленивыми перечислениями (Ruby >= 2.1) это гораздо приятнее, мы можем повторно использовать Enumerable#sorted?:

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

Ответ 2

Вы можете сравнить их пополам:

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

Ответ 3

уменьшить может сравнить каждый элемент с предыдущим и остановиться, когда он найдет один из нестандартных:

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

Ответ 4

Если окажется, что массив не отсортирован, будет ли ваше следующее действие всегда сортировать его? Для этого случая использования (хотя, конечно, в зависимости от количества раз, когда массив уже будет отсортирован), вы можете не захотеть проверить, отсортировано ли оно, но вместо этого просто выберите всегда сортировать массив. Сортировка уже отсортированного массива довольно эффективна при использовании многих алгоритмов и просто проверка того, отсортирован ли массив уже не так много, что делает проверку + сортировку более эффективной, чем просто сортировка.

Ответ 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

Ответ 6

Итерации по объектам и убедитесь, что каждый следующий элемент → = текущий элемент (или предыдущий - это & lt; =, очевидно) текущий элемент.

Ответ 7

Чтобы это эффективно работало, вы захотите сортировать во время вставки. Если вы имеете дело с уникальными элементами, SortedSet также является опцией.

Для уточнения, если мы исправим массив, чтобы разрешить сортировку вставки, мы можем сохранить массив в отсортированном состоянии:

class Array
  def add_sorted(o)
    size = self.size
    if size == 0
      self << o
    elsif self.last < o
      self << o
    elsif self.first > o
      self.insert(0, o)
    else
      # This portion can be improved by using a binary search instead of linear
      self.each_with_index {|n, i| if n > o; self.insert(i, o); break; end}
    end
  end
end

a = []
12.times{a.add_sorted(Random.rand(10))}
p a # => [1, 1, 2, 2, 3, 4, 5, 5, 5, 5, 7]

или использовать встроенную сортировку:

class Array
  def add_sorted2(o)
    self << o
    self.sort
  end
end

или, если вы имеете дело с уникальными элементами:

require "set"
b = SortedSet.new
12.times{b << Random.rand(10)}
p b # => #<SortedSet: {1, 3, 4, 5, 6, 7, 8, 9}>