Inserción de aprendizaje Ordenar en Ruby

Question

Acabo de comenzar el curso de introducción a algoritmos MIT a través del material publicado en línea. Junto con el curso, también he decidido aprender/mejorar mis habilidades Ruby mediante la codificación de los algoritmos que contiene.

estoy en el primer algoritmo dado, que es una especie de inserción, y he escrito el siguiente código, pero yo estoy recibiendo este error al ejecutarlo:

insertionsort.rb: 5: en ` > ': comparación de Fixnum con nula falló (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) 

estoy seguro de que es un problema bastante básico pero simplemente no puede comprender lo que es en este momento. Cualquier ayuda o consejo sería muy apreciado.

Answer 1

Estás sobrepasando los límites de tu matriz. El ejemplo que se le dio fue asumiendo matrices de 1 indización, pero las matrices en ruby ​​están 0 indexadas. La primera línea debe ser

for j in 1...num.length 

Answer 2

La otra respuesta es correcta que va más allá del final de los valores de la matriz, ya que está basado en 0, pero hay otros cambios que necesita hacer para hacer que el algoritmo :

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

y

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

Answer 3

sólo un complemento de menor importancia a los otros, excelentes respuestas:

Creo que ahora se acepta generalmente que la indexación de origen 0 tiene una serie de ventajas prácticas y empíricas sobre la indexación de 1 origen. La experiencia sugiere que simplemente "funciona mejor" y es menos propenso a errores.

Es por eso que muchos programadores enumeran las cosas desde cero y sorprenden a las personas "normales".

Answer 4

Aunque este ejercicio es muy fresco, de acuerdo con esta excelente entrada en el blog probablemente debería evitar la escritura de su propia especie y se basan en la incorporada en Array :: sort

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

Answer 5

La implementación más simple es algo así como esto:

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) 

Nota: para mejorar la eficacia del algoritmo, puede utilizar la búsqueda binaria para la comparación de elementos.

What Is Insertion Sort ?