Сортировка обучающей вставки в Ruby

Question

Я только начал курс «Введение в алгоритмы MIT» из материалов, размещенных в Интернете. Наряду с курсом я также решил изучить / улучшить свои навыки Ruby, кодируя алгоритмы в нем.

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

inserttionsort.rb: 5: in `> ': не удалось сравнить Fixnum с nil (ArgumentError)

def  insertionsort(num)
for j in 2..num.length
    key = num[j]
    i = j - 1
    while i > 0 and num[i] > key
        num[i+1] = num[i]
        i = i - 1
    end
    num[i+1] = key
end 
puts num
end

numbers = [23,34,46,87,12,1,66]

insertionsort(numbers)

Я уверен, что это довольно простая проблема, но я просто не могу понять, что это в данный момент. Любая помощь или советы будут очень признательны.

Answer 1

Другой правильный ответ: вы проходите через конец значений в массиве, потому что он основан на 0, но есть другие изменения, которые необходимо внести, чтобы алгоритм работал:

for j in 1..(num.length - 1)

и

while i >= 0 and num[i] > key

Answer 2

Вы выходите за границы вашего массива. В приведенном вами примере использовались массивы с 1 индексом, а массивы в ruby ​​- с 0 индексами. Первая строка должна быть

for j in 1...num.length

Answer 3

Самая простая реализация выглядит примерно так:

def insertion_sort(arr)
  for i in (1...(arr.size))
    if arr[i-1] > arr[i]
      i.downto(1) do |el|
        if arr[el] < arr[el-1]
          arr[el-1], arr[el] = arr[el], arr[el-1]
        end
      end
    end
  end
  arr
end

arr = [5, 2, 4, 6, 1, 3]

p insertion(arr)

Примечание: для повышения эффективности алгоритма вы можете использовать бинарный поиск для сравнения элементов.

Что такое вставка сортировки?

Answer 4

Хотя это упражнение действительно круто, согласно этому прекрасному сообщению в блоге, вам, вероятно, следует избегать написания своего рода и полагаться на встроенный Array :: sort

http://philcrissman.com/2010/07/18/how-not-to-write-sorting-algorithms-in-ruby/

Answer 5

Просто незначительное дополнение к другим, отличные ответы:

Я думаю, что в настоящее время общепризнанно, что индексация с 0 источниками имеет ряд практических и эмпирических преимуществ по сравнению с индексацией с 1 источником. Опыт показывает, что он просто «работает лучше» и менее подвержен ошибкам.

Вот почему многие программисты нумеруют вещи с нуля и удивляют "нормальных" людей.