Inserimento apprendimento Ordina in Ruby

Question

Ho appena iniziato il corso MIT Introduction to Algorithms attraverso il materiale pubblicato online. Insieme al corso ho anche deciso di imparare/migliorare le mie capacità di Ruby codificando gli algoritmi in esso contenuti.

Io sono il primo algoritmo di data, che è L'ordinamento per inserzione, e ho il seguente codice digitato su ma sto ottenendo questo errore quando l'eseguo:

insertionsort.rb: 5: in ` > ': confronto tra Fixnum con nil fallito (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) 

sono sicuro che si tratta di un problema piuttosto semplice, ma non riesco proprio a capire cosa è in questo momento. Qualsiasi aiuto o consiglio sarebbe molto apprezzato.

Answer 1

Si sta sovraccaricando i limiti del proprio array. L'esempio che ti è stato dato stava assumendo gli array a 1 indice, ma gli array in ruby ​​sono indicizzati a 0. La prima linea dovrebbe essere

for j in 1...num.length 

Answer 2

L'altra risposta è corretta che si sta andando oltre la fine dei valori nella matrice, perché è 0-based, ma ci sono altri cambiamenti che è necessario fare per rendere il lavoro algoritmo :

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

e

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

Answer 3

Solo un complemento minore agli altri, risposte eccellenti:

Penso che ora sia generalmente accettato che l'indicizzazione di origine 0 abbia un numero di vantaggi pratici ed empirici rispetto all'indicizzazione di 1 origine. L'esperienza suggerisce che "funziona meglio" ed è meno soggetto a errori.

Ecco perché molti programmatori numerano le cose da zero e stupiscono le persone "normali".

Answer 4

Anche se questo esercizio è davvero cool, in base a questo ottimo post del blog, probabilmente si dovrebbe evitare di scrivere il proprio ordinamento e fare affidamento sul costruito in Array :: sort

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

Answer 5

L'implementazione più semplice è qualcosa di simile this:

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: per migliorare l'efficienza dell'algoritmo, è possibile utilizzare la ricerca binaria per il confronto degli elementi.

What Is Insertion Sort ?