Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Insertionsort, Shakersort und Mergesort


Orpi - So 18.09.05 18:55
Titel: Insertionsort, Shakersort und Mergesort
hallo

ich habe einige sortieralgorithmen programmiert(bubblesort,selectionsort,quicksort,mergesort) und bleibe bei insertionsort und shakersort hängen.
ich habe zwar algorithmen nur liefern diese nicht das ergebnis das ich mir wünschen würde..nämlich einen sortieren array.

hier mal meine algorithmen

Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
 
procedure InsertionSort(anfang,ende:integer; SF : TSortFeld);// den array SF vom anfang bis ende sortieren
var i, j, hSF: integer;
begin
  for i:=anfang to ende-1 do begin
    j:=i;
    hSF:=SF[j]; // elemente merken
    while (j>0) and (SF[j-1]>hSF) do begin  // prüfen ob das gemerkte element kleiner als das betrachtete ist 
      SF[j]:=SF[j-1];// und gegebenenfalls austauchsen
      dec(j);
    end;
    SF[j]:=hSF;// s.o.
  end;
end;

bei insertionsort wird der gleiche array der reinkommt auch ausgegeben..keine ahnung wieso


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:
 
procedure shakerSort(anfang,ende:integer; SF : TSortFeld);
 var
 j,k:integer;
begin

repeat
  for j:=ende downto anfang do // von hinten nach vorn durchlaufen
  begin
    if SF[j-1]>SF[j] then  // überprüft das betrachtete und das vorhergehende  
    begin
     tausche(SF[j-1],SF[j]); // und vertaucht gegebenenfalls
     k:=j;
    end;
  end;
  ende:=k+1;
  for j:=anfang to ende do /läuft jetz vom anfang zum ende --> also entgegengesetzt der 1. schleife
  begin
    if SF[j-1]>SF[j] then // s.o.
    begin
    tausche (SF[j-1],SF[j]);// s.o.
          k:=j;
    end;
  end;
  ende:=k-1;
  until ende>anfang;
end;

procedure tausche(var a,b:TElement); // vertauscht die beidenen angegebenen elemente
var
h:TElement;
begin
  h:=a;
  a:=b;
  b:=h;
end;


AXMD - So 18.09.05 19:00
Zweiter Quelltext, Zeile 7: wieso downto? Abgesehen davon kenne ich die Algorithmen nicht oder nur wenig. Ein paar Kommentare wären evtl. nicht schlecht...

AXMD


Orpi - So 18.09.05 19:38
also ich weiss nach genauerer betrachtung auch nicht warum ich nun downto benutzt habe kann einer anderen lösung aber auch nicht herr werden.


nun zu kleinen erklärungen:

shakersort sortiert zahlenketten indem er sich jede zahl einzeln ansieht , sie mit der nächsten vergleicht und gegebenenfalls vertauscht. nun läuft er aber nicht jedesmal von vorn nach hiten sonder immer hin und her zwischen anfang und nede: ähnlich einer schüttelbewegung


insertionsort hingegen indem er sich eine zahl merk und diese mit allen zahlen die vor ihm stehen vergleicht und gegebenenfalss nach rechts verschiebt. so fügt er die zahlen der reihenach in die richtige position und lässt alles anderen elemente nachrücken


AXMD - So 18.09.05 19:48
Ömm... ich meinte eher Kommentare im Quelltext... es ist verdammt schwer, anderer Leute Quelltext zu lesen, wenn keine Kommentare drin sind ;)

AXMD


Orpi - So 18.09.05 19:56
s.o.


Orpi - So 18.09.05 21:14
ich hab mich auchnoch mit mergesort beschäftig aber acuh der weist macken auf die ich nich lokalisieren kann.
ich habe schon alles kommentiert..vielleicht kann mir auch damit jemand helfen?


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:
 
procedure mergesort(anfang,ende:integer;VAR SF: TSortFeld);
var i,j,k,mid:integer;
 hSF: TSortfeld;
begin
  if (ende-anfang>0) then begin //Abbruchbedingung für Rekursion

    // Mittleres Element bestimmen und rekursiver Abstieg
    mid := (ende+anfang) div 2;
    mergesort(anfang, mid,SF);
    mergesort(mid+1, ende,SF);

    // Mischen der sortierten Unterfelder
    // dabei wird ein Hilfsfeld hSF verwendet
    //   1. Daten in Hilfsfeld kopieren
    for i:=mid downto anfang do
      hSF[i] := SF[i];
    for j:=mid+1 to ende do
      hSF[ende+mid+1-j] := SF[j];

    //      Die Felder sind jetzt in hSF[] so angeordnet, dass sich die
    //      jeweils größten Elemente in der Mitte befinden
    //      i und j zeigen auf auf den linken, bzw. rechten Rand
    //    2. Mischen:
    for k:=anfang to ende do
    begin
      if hSF[i]<hSF[j] then begin
        SF[k]:=hSF[i];
        i:=i+1;
      end else begin
        SF[k]:=hSF[j];
        j:=j-1;
      end;
    end; // Ende von "for"
  end;   // Ende von "if" (Abbruchbedinung)
end;     // Ende von "procedure"


Grishnak - Mo 19.09.05 01:34
zu Insertion-Sort:

probier doch mal

Delphi-Quelltext 
1:
 
for i:=anfang+1 to ende

statt

Delphi-Quelltext 
1:
 
for i:=anfang to ende-1


Orpi - Mo 19.09.05 13:07
user profile iconGrishnak hat folgendes geschrieben:
zu Insertion-Sort:

probier doch mal

Delphi-Quelltext 
1:
 
for i:=anfang+1 to ende

statt

Delphi-Quelltext 
1:
 
for i:=anfang to ende-1




jetz gibt die procedure einfach das aus was reingekommen ist... :?: :shock:


Grishnak - Mo 19.09.05 14:16
Hier ist meine Version des Insertion-Sort-Algorithmus. Ich arbeite allerdings mit zwei ListBoxen, eine unsortierte, deren Werte zufällig gefüllt werden und einer sortierten (bzw. zu sortierenden):


Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
 
procedure TForm1.InsertButtonClick(Sender: TObject);
var
  Item: string;
  i, j: integer;
begin
  SortedListBox.Items.BeginUpdate;
  SortedListBox.Items.Text:=UnsortedListBox.Items.Text;

  for i:=1 to SortedListBox.Count-1 do
    begin
      j:=i;
      Item:=SortedListBox.Items[i];
      while (j > 0) and (SortedListBox.Items[j-1] > Item) do
        begin
          SortedListBox.Items[j]:=SortedListBox.Items[j-1];
          Dec(j);
        end;
      SortedListBox.Items[j]:=Item;
    end;

  SortedListBox.Items.EndUpdate;
end;


Das ganze funktioniert wunderbar!

Hier auch noch mein Merge-Sort-Algorithmus:


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:
 
procedure TForm1.MergeButtonClick(Sender: TObject);
  procedure MSort(l, r: integer);
    procedure Merge(const l, m, r: integer);
    var
      Items: array[0..NUMBER_OF_ELEMENTS-1] of string;
      i, j, k, h: integer;
    begin
      i:=l;
      j:=m+1;
      k:=l;
      while (i <= m) and (j <= r) do
        begin
          if SortedListBox.Items[i] <= SortedListBox.Items[j]
            then
              begin
                Items[k]:=SortedListBox.Items[i];
                Inc(i);
              end
            else
              begin
                Items[k]:=SortedListBox.Items[j];
                Inc(j);
              end;
          Inc(k);
        end;

      if i > m
        then for h:=j to r do Items[k+h-j]:=SortedListBox.Items[h]
        else for h:=i to m do Items[k+h-i]:=SortedListBox.Items[h];

      for h:=l to r do SortedListBox.Items[h]:=Items[h];
    end;
  var
    m: integer;
  begin
    if l < r
      then
        begin
          m:=(l+r) div 2;
          MSort(l, m);
          MSort(m+1, r);
          Merge(l, m, r);
        end;
  end;
begin
  SortedListBox.Items.BeginUpdate;
  SortedListBox.Items.Text:=UnsortedListBox.Items.Text;

  MSort(0, SortedListBox.Items.Count-1);

  SortedListBox.Items.EndUpdate;
end;


Orpi - Mo 19.09.05 14:48
ich hab deine version des insertionsort verfahren auf meine bedürfnisse zugeschnitten und komme auf den exakt gleichen algorithmus und dem exakt gleichem ergebnis:#
nämlich das der array der reinkommt auch genauso rauskommt


Grishnak - Mo 19.09.05 15:11
Mir deucht, der Fehler könnte hier liegen:


Delphi-Quelltext 
1:
 
procedure InsertionSort(anfang,ende:integer; var SF : TSortFeld);// den array SF vom anfang bis ende sortieren


Orpi - Mo 19.09.05 17:23
hab ich auch eben bemerkt *vorkopfhau* sowas beklopptes :lol:


Orpi - Mo 19.09.05 18:15
jetzt funktioniert alles wie ich es will..die einzige ausnahme ist mergesort..ioch werd einfach nicht schlau aus dem algorithmus...irgendwas ist noch falsch


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:
 
procedure mergesort(anfang,ende:integer;VAR SF: TSortFeld);
var i,j,k,mid:integer;
 hSF: TSortfeld;
begin
  if (ende-anfang>0) then begin //Abbruchbedingung für Rekursion
    // Mittleres Element bestimmen und rekursiver Abstieg
    mid := (ende+anfang) div 2;
    mergesort(anfang, mid,SF);
    mergesort(mid+1, ende,SF);

    // Mischen der sortierten Unterfelder
    // dabei wird ein Hilfsfeld hSF verwendet
    //   1. Daten in Hilfsfeld kopieren
    for i:=mid downto anfang do
      hSF[i] := SF[i];
    for j:=mid+1 to ende do
      hSF[ende+mid+1-j] := SF[j];

    //      Die Felder sind jetzt in hSF[] so angeordnet, dass sich die
    //      jeweils größten Elemente in der Mitte befinden
    //      i und j zeigen auf auf den linken, bzw. rechten Rand
    //    2. Mischen:
    for k:=anfang to ende do
    begin
      if hSF[i]<hSF[j] then begin
        SF[k]:=hSF[i];
        i:=i+1;
      end else begin
        SF[k]:=hSF[j];
        j:=j-1;
      end;
    end; // Ende von "for"
  end;   // Ende von "if" (Abbruchbedinung)
end;     // Ende von "procedure"


Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 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!