Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Sortieralgorithmus - Wo ist der Fehler?


Gorthaur - Fr 03.03.06 18:14
Titel: Sortieralgorithmus - Wo ist der Fehler?
Tach!

Ich habe einen Algorithmus zum Sortieren eines Arrays. Dieses Array (of integer) ist gefüllt mit Zahlen welche nach Durchführung des Algorithmus der Größe nach sortiert sein sollten.

Der Algorithmus sollte eigendlich funktionieren, da ich die Vorlage dazu aus einem alten Prog. geklaut habe. Aber irgendwo scheint ein Fehler zu sein da sich die Reihenfolge der Elemente des Arrays zwar verändern, aber nicht nach Größe sortiert werden...

Ich bin schon seit einer halben Ewigkeit auf der Suche nach dem Fehler aber kann ihn einfach nicht finden. Vielleicht sieht ja eine/r von euch mehr als ich?

Hier der Algorithmus (n = Anzahl der Elemente im Array, liste = array of integer, Ausgabe erfolgt im HP):


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:
 
procedure Sortieren(n: integer; var feld:liste);
var
  l, r      : word;
  X1, help  : integer;
begin
  if n<2 then writeln ('Eine Umsortierung fuer n<2 ist nicht moeglich !');
  readln;
  X1 := feld[1]; l := 2; r := n;
  while l < r do
  begin
    while (feld[l]  < X1) and (l < r) do inc(l);
    while (feld[r] >= X1) and (l < r) do dec(r);
    if l < r then
    begin
      help    := feld[l];
      feld[l] := feld[r];
      feld[r] := help;
      inc(l); dec(r);
    end;
  end;
  if feld[r] >= X1 then dec(r);
     feld[1] := feld[r];
     feld[r] := X1;
end;


Schonmal THX für die Mühe!


Moderiert von user profile iconraziel: Topic aus Sonstiges (Delphi) verschoben am Fr 03.03.2006 um 19:02


Martin1966 - Fr 03.03.06 18:28
Kann es sein (wenn ich so die Einrückungen sehen), dass am Ende ein BEGIN und END fehlt?
Also so:

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:
 
procedure Sortieren(n: integer; var feld:liste); 
var 
  l, r      : word; 
  X1, help  : integer; 
begin 
  if n<2 then writeln ('Eine Umsortierung fuer n<2 ist nicht moeglich !'); 
  readln; 
  X1 := feld[1]; l := 2; r := n; 
  while l < r do 
  begin 
    while (feld[l]  < X1) and (l < r) do inc(l); 
    while (feld[r] >= X1) and (l < r) do dec(r); 
    if l < r then 
    begin 
      help    := feld[l]; 
      feld[l] := feld[r]; 
      feld[r] := help; 
      inc(l); dec(r); 
    end; 
  end; 
  
  if feld[r] >= X1 then 
  begin
     dec(r); 
     feld[1] := feld[r]; 
     feld[r] := X1; 
  end;
end;


Gorthaur - Fr 03.03.06 18:45
Nein, die Version ohne begin und end ist wohl richtig.

Ich hab' gerade mal durchlaufen lassen, es macht auch scheinbar keinen Unterschied...


Martin1966 - Fr 03.03.06 18:47
Welcher Sortieralgorithmus soll das überhaupt sein?


Gorthaur - Fr 03.03.06 18:53
Keine Ahnung wie man diesen Algorithmus nennt, oder ob der überhaupt einen Namen hat...


Martin1966 - Fr 03.03.06 18:59
Dann such doch mal nach einem anderen, funktionierenden Suchalgo.

Am einfachsten (aber leider auch am langsamsten) wäre wohl dieser hier:

Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
 
Type
  TIntegerList : Array of Integer;

procedure Sortieren (var Liste: TIntegerList);  
var  
  loop1, loop2: integer;
  swap: integer;  
begin  
  for loop1 := Low (Liste) to High (Liste) Do
    for loop2 := Loop1 +1 to High (Liste) Do
      if Liste[loop1] < Liste[Loop2] then
        begin
          swap := Liste[loop1];
          Liste[loop1] := Liste[loop2];
          Liste[loop2] := swap;
        end;
end;


Aber vorsicht. Ich hab den Code nicht getestet!!

Lg Martin


Gorthaur - Fr 03.03.06 19:08
Danke für die Alternative, aber im Rahmen meiner Klausurvorbereitung bräuchte ich eine funktionierende Version meines Alegorithmus...


MightyPit - Mo 13.03.06 19:13
Ich hab mir deinen Algo jetzt einige Zeit angeschaut, aber ich verstehs überhaupt nicht. der X1 Variablen soll der inhalt des ersten Feldes des Arrays übergegeben werden nehm ich an, dann müsstest du aber feld[0] adressieren. und wenn l eins höher als feld[0] sein soll muss l:=1 sein. Das erkennt man leider bei dem Font des Delphi-Quotes nur sehr schwer. Ich weiss nicht ob man das umstellen kann.
Vielleicht postest du am besten auch noch deine "Vorlage", damit wir etwas schlauer werden :)


Freiberger - Mo 13.03.06 19:29
Suche doch mal in Google nach QuickSort.
Im Delphi Easy-Helper is es auch beschrieben...
Das ist richtig schnell und ähnelt sehr stark deinem Code...


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!