Entwickler-Ecke
Delphi Language (Object-Pascal) / CLX - Straight Insertion (Sortierverfahren)
Stread - So 22.03.09 18:40
Titel: Straight Insertion (Sortierverfahren)
Ich beschäftige mich gerade mit Straight Insertion. Theoretisch habe ich verstanden wie diese Sortierung funktioniert, doch dann wollte ich es programmieren und es hat nicht geklappt. Also habe ich im Netz was gefunden.
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:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
| unit Unit1;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls, Grids;
type
TForm1 = class(TForm)
Button1: TButton;
Button2: TButton;
StringGrid1: TStringGrid;
procedure Sort;
procedure FormCreate(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
private
public
end;
var
Form1: TForm1;
a: array[0..5] of integer;
implementation
{$R *.DFM}
procedure TForm1.Sort;
var i,j,x,n: integer;
begin
for i := 2 to 5 do
begin
x := a[i];
a[0] := x;
j := i - 1;
while x < a[j] do
begin
a[j+1] := a[j];
j := j - 1;
end;
a[j+1] := x;
stringgrid1.RowCount :=stringgrid1.RowCount + 1;
for n := 0 to 4 do
begin
stringgrid1.Cells[n,stringgrid1.rowcount-1] := inttostr(a[n+1]);
end;
end;
end;
procedure TForm1.FormCreate(Sender: TObject);
begin
randomize;
end;
procedure TForm1.Button1Click(Sender: TObject);
var i: integer;
begin
stringgrid1.RowCount := 1;
for i := 0 to 4 do
begin
a[i+1] := random(200);
stringgrid1.Cells[i,0] := inttostr(a[i+1]);
end;
end;
procedure TForm1.Button2Click(Sender: TObject);
begin
sort;
end;
end. |
Bild zu dem Programm habe ich beigelegt.
Leider verstehe ich davon nicht allzuviel :?
Geht es nur auf diese Weise? Oder auch auf einer die weniger kompliziert ist? :P
Mir geht es hier nur um die Procedure TForm1.Sort
Zeile 40: das x ist nach meiner überlegung (die falsch ist) nie kleiner als j und das ganz danach ist doch sinnlos da es danach doch wieder gleich groß ist?
Kann mir das bitte einer erklären?
JayEff - So 22.03.09 18:58
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:
| procedure TForm1.Sort;
var
i, j, x, n: integer;
begin
for i := 2 to 5 do
begin
x := a[i];
a[0] := x;
j := i - 1;
while x < a[j] do
begin
a[j+1] := a[j];
j := j - 1;
end;
a[j+1] := x;
stringgrid1.RowCount :=stringgrid1.RowCount + 1;
for n := 0 to 4 do
begin
stringgrid1.Cells[n,stringgrid1.rowcount-1] := inttostr(a[n+1]);
end;
end;
end; |
Damit ich das auch verstehe, hab ich mal die Einrückung repariert... ;)
Wenn ich das richtig sehe, geht in (bei mir) Zeile 8 das Element a[0] verloren? :shock: x ist das zweite Element des Arrays. Geprüft wird dann in Zeile 11, ob das zweite Element x kleiner ist als das j-te Element a[j] (wobei j=1 am Anfang). Solange das zutrifft, wird das Element a[j+1] gelöscht und a[j] reingeschrieben, dann wird j um 1 verkleinert. (nach dem ersten Durchlauf der while-Schleife ist es also 0) a[0] ist auf a[2] gesetzt worden, a[2] ist inzwischen auf a[1] gesetzt. x = (früher a[2] = ) a[0] also ist die Abfrage x < a[j] (=a[0]) false.
Diese Paar Schritte der Prozedur hatten jetzt schon 2 mal einen Informationsverlust, zuerst verlieren wir den Inhalt von a[0], dann den von a[2] - ah halt, nein, a[2] wird in x gespeichert, welches dann in a[1] gespeichert wird in Zeile 17. Naja. Einen Informationsverlust. Das sortieren müsste also eigentlich schief gehen ... :shock:
Sicher dass der Code so 1:1 stimmt? :gruebel:
ub60 - So 22.03.09 19:57
Etwas kürzer geht es schon, viel einfacher leider nicht. Hier die kürzeste Variante.
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
| procedure TForm1.Sort;
var i , j : integer;
begin
for i := 2 to 5 do
begin
a[0] := a[i];
j := i-1;
while a[0] < a[j] do
begin
a[j+1] := a[j];
j := j - 1;
end;
a[j+1] := a[0];
StringGrid1.RowCount :=StringGrid1.RowCount + 1;
for j := 0 to 4 do
StringGrid1.Cells[j,StringGrid1.rowcount-1] := IntToStr(a[j+1]);
end;
end; |
ub60
Stread - So 22.03.09 20:15
Ja, der Code ist Original Copy&Paste. Hier nochmal die exe angehängt. Eben weil man was an Information verliert haeb ich da nicht ganz durchgeblickt.
Gibt es nur diese Variante oder gibt es noch einen anderen Weg?
ub60 - So 22.03.09 21:17
 Stread hat folgendes geschrieben  : |
| Gibt es nur diese Variante oder gibt es noch einen anderen Weg? |
Die Variante von mir ist die kürzeste Variante. Man speichert hier den Merkwert in a[0].
Eine andere Variante speichert in einer Merkvariablen, muss dann aber zwei Abfragen zur Ermittlung des Schleifenendes ausführen:
-Ist die Einfügeposition schon erreicht?
-Bin ich schon am Arrayanfang angekommen?
Insofern ist Deine Variante so ein Mischmasch.
ub60
Stread - So 22.03.09 22:49
Also ist deine Variante die beste?
ub60 - Mo 23.03.09 00:08
| Stread hat folgendes geschrieben : |
| Also ist deine Variante die beste? |
Die "beste" Variante von Insertionsort schon, ansonsten würde ich mehr zu Shell- oder Quicksort tendieren (je nach konkreter Anforderung).
ub60
JayEff - Mo 23.03.09 03:51
| ub60 hat folgendes geschrieben : |
| Stread hat folgendes geschrieben : | | Also ist deine Variante die beste? |
Die "beste" Variante von Insertionsort schon, ansonsten würde ich mehr zu Shell- oder Quicksort tendieren (je nach konkreter Anforderung).
ub60 |
Da gäbe es noch
HEAPSORT was einen besseren worst-case O(n * log(n)) hat aber in den meisten Fällen langsamer ist als Quicksort oder
INTROSORT als beste Alternative :zustimm:
Stread - Mo 23.03.09 19:34
Ich muss aber Straight Insertion lernen.
Ich hätte dazu noch ein paar fragen wenns recht ist. :D
Ich nehme die Variante von ub60
Wenn ich als Beispiel die 5 Zahlen 30 , 24, 17 , 5 , 3 habe ist dann a[0] 24 und a[j] 30 ? a[0] ist immer die aktuelle Zahl wo wir gerade dabei sind sie zu sortieren also am Anfang die 24 und danach die 17 und j ist immer die Zahl davor? Bei zeile 8 wird dann verglichen ob die aktuelle Zahl kleiner ist als die davor?
Wenn Ja, ist die zweite Zahl dann die erste Zahl? Ist a[0] nun die erste Zahl?
Ist bei Zeile j beim ersten Durchlauf 0?
Danke für die Beantwortung :flehan:
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!