Entwickler-Ecke
Delphi Language (Object-Pascal) / CLX - Shellsort - Erklärung gesucht
Marzl89 - Di 24.06.08 22:29
Titel: Shellsort - Erklärung gesucht
Hallo,
ich bin neu hier. Könnte mir vllt einer diese prozedure erklären bitte.
Danke schön im Vorraus!
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26:
| procedure TForm1.ShellSort; var i, j, h, v: integer; begin h := 1; repeat h := ( 3 * h ) + 1; until h > length(ZFeld); repeat h := ( h div 3 ); for i := h + 1 to length(ZFeld) do begin v := ZFeld[i - 1]; j := i; while ( ( j > h ) and ( ZFeld[j - h - 1] > v ) ) do begin versuche:=versuche+1; ZFeld[j - 1] := ZFeld[j - h - 1]; dec( j, h ); end; ZFeld[j - 1] := v; end; until h = 1; end; |
Moderiert von
Narses: Delphi-Tags hinzugefügt
Nostromo - Mi 25.06.08 00:00
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31:
| procedure TForm1.ShellSort; var i, j, h, v: integer; begin h := 1; repeat h := ( 3 * h ) + 1; until h > length(ZFeld); repeat h := ( h div 3 ); for i := h + 1 to length(ZFeld) do begin v := ZFeld[i - 1]; j := i; while ( ( j > h ) and ( ZFeld[j - h - 1] > v ) ) do begin versuche:=versuche+1; ZFeld[j - 1] := ZFeld[j - h - 1]; dec( j, h ); end; ZFeld[j - 1] := v; end; until h = 1; end; |
Das ganze soll wohl einen Sortier-Algorithmus darstellen.
Allerdings funktioniert er , soweit ich es testen konnte, nicht.
Eine Zahl bleibt immer unsortiert stehen.
Ein Beispiel für einen funkionierenden Algorithmus wäre der Bubble-Sort:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18:
| procedure BubbleSort(Items: TStrings); var done: boolean; i, n: integer; Dummy: string; begin n := Items.Count; repeat done := true; for i := 0 to n - 2 do if Items[i] > Items[i + 1] then begin Dummy := Items[i]; Items[i] := Items[i + 1]; Items[i + 1] := Dummy; done := false; end; until done; end; |
Diese Funktion müsste natürlich für ein Array wie du es benötigst angepaßt werden.
Weitere Links hierzu:
http://de.wikipedia.org/wiki/Bubblesort
http://www.delphi-treff.de/tipps/algorithmen/
http://www.wer-weiss-was.de/theme9/article230844.html
Moderiert von
Narses: Code- durch Delphi-Tags ersetzt
Gausi - Mi 25.06.08 08:41
Hallo und :welcome: in der Entwickler-Ecke
@Nostromo: Wenn man bei Shellsort Hilfe braucht, ist Bubblesort kaum die richtige Antwort. ;-)
@Marzl89: Shellsort fand ich schon immer etwas doof, aber warum startest du die for-Schleife bei h+1? Sollte die nicht lieber bei h (oder sogar bei 0) starten?
Marzl89 - Mi 25.06.08 18:15
danke für die Hilfe. Naja ich hatte das so gefunden, weil wir das noch nicht hatten. Ich hab mir den Quelltext aus dem Intergezogen gehabt.
Wenn es jedoch einen besseren für Shellsort gibt, der einfacher ist. Dann würde ich mich darüber auch freuen.
Gausi - Mi 25.06.08 19:14
Hat das denn geklappt? Das war mehr oder weniger ins Blaue geraten.
Shellsort ist das Verfahren, was irgenwie zwischen den langsamen Verfahren (Bubblesort, Einfügesort, etc.) und den schnellen Verfahren (Quicksort, Mergesort, Heapsort) liegt. Mir schwirrt da irgendso eine Aussage im Kopf rum wie "wenn man für h alle Werte der Form 3n+1 und 5n+1 wählt, dann ist die Laufzeit ganz toll, ansonsten eher nicht so". Deswegen finde ich den etwas doof. Schwer zu implementieren, und bringt irgendwie doch nichts. ;-)
ub60 - Mi 25.06.08 20:31
Marzl89 hat folgendes geschrieben: |
d
Wenn es jedoch einen besseren für Shellsort gibt, der einfacher ist. Dann würde ich mich darüber auch freuen. |
Einfachere Shellsort-Implementierungen gibt es schon. Schnellere und einfachere hingegen kaum.
Gausi hat folgendes geschrieben: |
Mir schwirrt da irgendso eine Aussage im Kopf rum wie "wenn man für h alle Werte der Form 3n+1 und 5n+1 wählt, dann ist die Laufzeit ganz toll, ansonsten eher nicht so". Deswegen finde ich den etwas doof. Schwer zu implementieren, und bringt irgendwie doch nichts. ;-) |
Das stimmt nur bedingt. Es gibt zum Beispiel Untersuchungen der Abstände
- 1, 3, 7, 15, 31, 63, 127, ..., 2^j - 1 von Papernov/Stasevic,
- 1, 2, 3, 4, 6, 8, 9, 12, 16, ..., 2^p3^q von Pratt,
- 1, 3, 7, 21, 48, 112, 336, 861, 1968, 4592, 13776, 33936, 86961, 198768, 463792, 1391376 von Sedgewick
Diese Abstände sortieren auch sehr schnell.
Die Geschwindigkeit von Shellsort beruht auf 2 Zusammenhängen:
Zuerst ist hier das implementierte (innere) Sortierverfahren zu nennen. Im obigen Quelltext ist dies Insertionsort. Es kann aber auch Bubblesort oder Selectionsort sein.
Außerdem ist der Abstand h von wesentlicher Bedeutung. Er gibt an, in welchen Abstand die Elemente zueinander liegen, die vom inneren Verfahren vorsortiert werden.
ub60
Gausi - Mi 25.06.08 23:17
ub60 hat folgendes geschrieben: |
- 1, 2, 3, 4, 6, 8, 9, 12, 16, ..., 2^p3^q von Pratt,
|
Jetzt wo ich es lese: Das ist das Rumgeschwirre aus meinem Kopf. ;-)
ub60 - Mi 25.06.08 23:41
Gausi hat folgendes geschrieben: |
Jetzt wo ich es lese: Das ist das Rumgeschwirre aus meinem Kopf. ;-) |
Wenn DAS in Deinem Kopf rumschwirrt, würde ich auch Bedenken haben :D :D
ub60
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!