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); //Wenn h kleiner als das Zahlenfeld ist,
                        // dann wiederholen
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;  //Für jedes Vertauschen der Zahlen,
                      // wir Versuche um 1 erhöht

ZFeld[j - 1] := ZFeld[j - h - 1];
dec( j, h );
end;
ZFeld[j - 1] := v;
end;
until
h = 1;
end;


Moderiert von user profile iconNarses: 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;  
  // Hier wird wohl der Zeiger "h" solange erhöht, bis das Ende des Strings ZFeld übersprungen wurde.
  repeat  
    h := ( 3 * h ) + 1;
  until h > length(ZFeld); //Wenn h kleiner als das Zahlenfeld ist, dann wiederholen  
  repeat
    // Hier wird wieder auf den letzten gültigen Wert von "h" zurückgesprungen
    h := ( h div 3 ); 
    // Hier scheint eine Art Austausch von Zahlen stattzufinden wobei auf die Größe der Zahlen als 
    // Grund des Tausches geprüft wird.
    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  
        // Die Variable versuche ist hier nicht definiert?
        // und falls die Variable woanders deklariert wurde ist noch die Frage ob sie
        // vor dieser Stelle initialisiert worden ist. (d.h. mit einem Startwert versehen wurde.)
        versuche:=versuche+1;  //Für jedes Vertauschen der Zahlen, wir Versuche um 1 erhöht  
        ZFeld[j - 1] := ZFeld[j - h - 1];  
        dec( j, h );  
      end;  
      ZFeld[j - 1] := v;  
    end;  
  until h = 1// solange bis h wieder 1 ist.
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 + 1then      
    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 user profile iconNarses: 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

user profile iconMarzl89 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.

user profile iconGausi 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

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

user profile iconub60 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

user profile iconGausi 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