Straight Insertion (Sortierverfahren)

Stread · Beiträge: 188 Win 7 Delphi XE

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.

markieren

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
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  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?

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?

Einloggen, um Attachments anzusehen!

JayEff · Beiträge: 2971 Windows Vista Ultimate D7 Enterprise

markieren

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 · Beiträge: 764 Erhaltene Danke: 127

Etwas kürzer geht es schon, viel einfacher leider nicht. Hier die kürzeste Variante.

markieren

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 · Beiträge: 188 Win 7 Delphi XE

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?

Einloggen, um Attachments anzusehen!

ub60 · Beiträge: 764 Erhaltene Danke: 127

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 · Beiträge: 188 Win 7 Delphi XE

Also ist deine Variante die beste?

ub60 · Beiträge: 764 Erhaltene Danke: 127

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 · Beiträge: 2971 Windows Vista Ultimate D7 Enterprise

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 Suche in Wikipedia

HEAPSORT was einen besseren worst-case O(n * log(n)) hat aber in den meisten Fällen langsamer ist als Quicksort oder Suche in Wikipedia

INTROSORT als beste Alternative :zustimm:

_________________
>+++[>+++[>++++++++<-]<-]<++++[>++++[>>>+++++++<<<-]<-]<<++
[>++[>++[>>++++<<-]<-]<-]>>>>>++++++++++++++++++.+++++++.>++.-.<<.>>--.<+++++..<+.

Stread · Beiträge: 188 Win 7 Delphi XE

Ich muss aber Straight Insertion lernen.

Ich hätte dazu noch ein paar fragen wenns recht ist.

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:

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme