Insertionsort, Shakersort und Mergesort

Orpi · Beiträge: 24

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

markieren

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

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:

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 · Verfasst: 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 · Beiträge: 24

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 · Verfasst: 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 · Beiträge: 24

s.o.

Orpi · Beiträge: 24

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?

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:

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 · Beiträge: 221 Windows XP Home Delphi 7 PE, Delphi 2005 PE

zu Insertion-Sort:

probier doch mal

markieren

Delphi-Quelltext

1:	for i:=anfang+1 to ende

statt

markieren

Delphi-Quelltext

1:	for i:=anfang to ende-1

_________________
Mach' etwas idiotensicher und irgendjemand erfindet einen besseren Idioten!

Orpi · Beiträge: 24

Grishnak hat folgendes geschrieben:

zu Insertion-Sort:

probier doch mal

markieren

Delphi-Quelltext

1:	for i:=anfang+1 to ende

statt

markieren

Delphi-Quelltext

1:	for i:=anfang to ende-1

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

Grishnak · Beiträge: 221 Windows XP Home Delphi 7 PE, Delphi 2005 PE

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

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:

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:

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:

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;

_________________
Mach' etwas idiotensicher und irgendjemand erfindet einen besseren Idioten!

Orpi · Beiträge: 24

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 · Beiträge: 221 Windows XP Home Delphi 7 PE, Delphi 2005 PE

Mir deucht, der Fehler könnte hier liegen:

markieren

Delphi-Quelltext

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

_________________
Mach' etwas idiotensicher und irgendjemand erfindet einen besseren Idioten!

Orpi · Beiträge: 24

hab ich auch eben bemerkt *vorkopfhau* sowas beklopptes :lol:

Orpi · Beiträge: 24

jetzt funktioniert alles wie ich es will..die einzige ausnahme ist mergesort..ioch werd einfach nicht schlau aus dem algorithmus...irgendwas ist noch falsch

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:

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"

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme