Autor |
Beitrag |
Marzl89
Hält's aus hier
Beiträge: 2
|
Verfasst: Di 24.06.08 22:29
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
      
Beiträge: 33
Erhaltene Danke: 1
Win 7 Pro 64bit, Win XP SP3
Delphi 7 Ent
|
Verfasst: Mi 25.06.08 00:00
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:
de.wikipedia.org/wiki/Bubblesort
www.delphi-treff.de/tipps/algorithmen/
www.wer-weiss-was.de...9/article230844.html
Moderiert von Narses: Code- durch Delphi-Tags ersetzt
|
|
Gausi
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Mi 25.06.08 08:41
Hallo und  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?
_________________ We are, we were and will not be.
|
|
Marzl89 
Hält's aus hier
Beiträge: 2
|
Verfasst: 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
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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. 
_________________ We are, we were and will not be.
|
|
ub60
      
Beiträge: 764
Erhaltene Danke: 127
|
Verfasst: 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
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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. 
_________________ We are, we were and will not be.
|
|
ub60
      
Beiträge: 764
Erhaltene Danke: 127
|
Verfasst: Mi 25.06.08 23:41
|
|
|