Autor Beitrag
Marzl89
Hält's aus hier
Beiträge: 2



BeitragVerfasst: 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!

ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 33
Erhaltene Danke: 1

Win 7 Pro 64bit, Win XP SP3
Delphi 7 Ent
BeitragVerfasst: Mi 25.06.08 00:00 
ausblenden volle Höhe 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:
ausblenden 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:

de.wikipedia.org/wiki/Bubblesort
www.delphi-treff.de/tipps/algorithmen/
www.wer-weiss-was.de...9/article230844.html

Moderiert von user profile iconNarses: Code- durch Delphi-Tags ersetzt
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: 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?

_________________
We are, we were and will not be.
Marzl89 Threadstarter
Hält's aus hier
Beiträge: 2



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 764
Erhaltene Danke: 127



BeitragVerfasst: 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
  • 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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: 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. ;-)

_________________
We are, we were and will not be.
ub60
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 764
Erhaltene Danke: 127



BeitragVerfasst: 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