Einführung in die Lernumgebung Sortieren in Ruby

Question

Ich habe gerade den Kurs MIT Einführung in Algorithmen durch das Online-Material gestartet. Neben dem Kurs habe ich mich auch entschieden, meine Ruby-Fähigkeiten zu verbessern, indem ich die darin enthaltenen Algorithmen kodiere.

Ich bin auf dem ersten Algorithmus gegeben, die Insertion Art ist, und ich habe den folgenden Code eingegeben hat, aber ich bin immer diese Fehlermeldung, wenn ich es laufen:

insertionsort.rb: 5: in ` > ': Vergleich von Fixnum mit Null fehlgeschlagen (Argumente)

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) 

ich bin sicher, dass es ein recht einfaches Problem ist, aber ich kann einfach nicht begreifen, was es im Moment ist. Jede Hilfe oder Tipps würden sehr geschätzt werden.

Answer 1

Sie überschreiten die Grenzen Ihres Arrays. Das Beispiel, das Sie erhielten, ging von 1-indizierten Arrays aus, aber Arrays in Ruby sind 0-indexiert. Die erste Zeile soll

for j in 1...num.length 

Answer 2

sein Die andere Antwort ist richtig, dass Sie in der Anordnung nach dem Ende der Werte gehen, weil es 0-basiert ist, aber es gibt auch andere Änderungen, die Sie benötigen, um die Algorithmus Arbeit zu machen :

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

und

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

Answer 3

nur eine kleine Ergänzung zu den anderen, sehr guten Antworten:

Ich glaube, es ist mittlerweile allgemein akzeptiert, dass die 0-Origin-Indexierung eine Reihe von praktischen und empirischen Vorteilen gegenüber der 1-Origin-Indexierung bietet. Die Erfahrung zeigt, dass es einfach "besser funktioniert" und weniger fehleranfällig ist.

Das ist der Grund, warum eine Menge Programmierer die Dinge von Null an zählen und "normale" Leute in Erstaunen versetzen.

Answer 4

Während diese Übung wirklich cool ist, nach diesem ausgezeichneten Blog-Post sollten Sie wahrscheinlich Ihre eigene Art vermeiden Schreiben und stützen sich auf die in Array gebaut :: sort

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

Answer 5

Die einfachste Implementierung ist so etwas wie dies:

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) 

Hinweis: um die Effizienz des Algorithmus zu verbessern, können Sie die binäre Suche nach Elementen Vergleich verwenden.

What Is Insertion Sort ?