Hallo, ich sollte als Aufgabe den Shellshort programmieren.
Doch ich habe noch ein paar Verständissfragen.
Zuerst einmal verstehe ich nicht mal ganz die Schrittweite berechnung :noe:
1,4,13,40,121,364,... -> allgemein h[k] = 3 x h[k-1]+1; h[1]=1
dabei bedeutet h[k] die Schrittweite der kten Sortierung.
Das heisst für mich mit der Schrittweite 13 "3 x 13[3-1] +1" Ist ja der 3 Durchgang
Nur leider ergibt das 79 anstatt 40?
Hingegen wenn ich immer die vorgehende Schrittweite nehme und rechne 3 x 13 +1 = 40 Dann stimmt es immer? Also kann ich auch diese Vorgehensweise nehmen?
Doch nun komm ich gleich zum nächsten Problem. Eigentlich muss ich ja mit der höchsten Zahl beginnen. Das heisst ich brauche ja eine Formel um den nächst kleineren Schritt auszurechenen.
Warum erhalten wir dann diese Formel h[k] = 3 x h[k-1]+1; h[1]=1?
Denn wenn ich es das im Java programmier brauch ich ja eine Formel um die Schrittweite jedesmal zu reduzieren bis auf 1 runter?
Die eigentliche Vorgehensweise von Shellshort geht so.
Man nimmt jede, sagen wir mal jede 13 Zahl. Das gibt dann ein paar Gruppen.
Diese Gruppen sortiert man nun.
Danach macht man wieder Gruppen mit jeder 4 Zahl.Die enstandenen Gruppen sortiert man wieder mit direktes Einfügen.
Das macht man bis man den 1 Schritt hat.
Um diese Gruppen zu sortieren brauche ich keine zusätzliche Arrays,oder? Ich kann gleich alle Zahlen an die richtigen Stellen verschieben?
So ich hoffe man hat meine 2-3 Fragen verstanden
Doch ich habe noch ein paar Verständissfragen.
Zuerst einmal verstehe ich nicht mal ganz die Schrittweite berechnung :noe:
1,4,13,40,121,364,... -> allgemein h[k] = 3 x h[k-1]+1; h[1]=1
dabei bedeutet h[k] die Schrittweite der kten Sortierung.
Das heisst für mich mit der Schrittweite 13 "3 x 13[3-1] +1" Ist ja der 3 Durchgang
Nur leider ergibt das 79 anstatt 40?
Hingegen wenn ich immer die vorgehende Schrittweite nehme und rechne 3 x 13 +1 = 40 Dann stimmt es immer? Also kann ich auch diese Vorgehensweise nehmen?
Doch nun komm ich gleich zum nächsten Problem. Eigentlich muss ich ja mit der höchsten Zahl beginnen. Das heisst ich brauche ja eine Formel um den nächst kleineren Schritt auszurechenen.
Warum erhalten wir dann diese Formel h[k] = 3 x h[k-1]+1; h[1]=1?
Denn wenn ich es das im Java programmier brauch ich ja eine Formel um die Schrittweite jedesmal zu reduzieren bis auf 1 runter?
Die eigentliche Vorgehensweise von Shellshort geht so.
Man nimmt jede, sagen wir mal jede 13 Zahl. Das gibt dann ein paar Gruppen.
Diese Gruppen sortiert man nun.
Danach macht man wieder Gruppen mit jeder 4 Zahl.Die enstandenen Gruppen sortiert man wieder mit direktes Einfügen.
Das macht man bis man den 1 Schritt hat.
Um diese Gruppen zu sortieren brauche ich keine zusätzliche Arrays,oder? Ich kann gleich alle Zahlen an die richtigen Stellen verschieben?
So ich hoffe man hat meine 2-3 Fragen verstanden