Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Quicksort-Suche einfaches programmierbares Beispiel


Paulus - Do 19.05.05 19:03
Titel: Quicksort-Suche einfaches programmierbares Beispiel
Abend!
Ich suche ein sehr einfaches Beispiel wie man das Prinzip des Quicksorts in Delphi umsetzen kann.
Zum Beispiel könnte ich mir folgendes vorstellen: Man gibt einige beliebige Zahlen in ein Edit-Feld ein und diese werden in eine Liste geschrieben. Quicksort sortiert dann die Zahlen in der Liste und gibt sie anschließend der Größe nach sortiert wieder aus. Nur leider habe ich wenig bis gar keine Ahnung wie der Sortier-Algorithmus dazu aussehen muss. Könnt ihr mir da weiterhelfen?
Ich bin dankbar für jede Hilfe :)


Moderiert von user profile iconraziel: Topic aus Sonstiges verschoben am Do 19.05.2005 um 19:13


delfiphan - Do 19.05.05 19:05

Quicksort ist z.B. in der Source-Datei classes.pas implementiert. Man findet ihn auch im Google.


Gausi - Do 19.05.05 19:15

Wozu denn in die Ferne schweifen? Sieh, das Gute liegt so nah [http://www.delphi-forum.de/viewtopic.php?t=35313&highlight=quicksort]!


Paulus - Do 19.05.05 19:15

wo finde ich die classes.pas-datei? In meinem Delphi-Ordner ist sie schon mal nicht ...


delfiphan - Do 19.05.05 19:18

Je nach Version ist die vielleicht nicht dabei. Bei mir ist sie unter %delphi%\source\rtl\common\classes.pas.
Oder ganz einfach: Control+Click auf "TList" in deinem Source und die classes.pas wird automatisch geladen.


Paulus - Mo 23.05.05 12:15

Hi. Also ich habe endlich ein Quelltext im Internet gefunden, den ich nachvollziehen kann:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
procedure sortieren(var aa: array of real; von,bis:integer);
  //Quicksort rekursiv
  var i,j: integer; //vor dem 13.02.2002 fälschlicherweise byte
  wertDerMitte:real;
begin
  i:=von;
  j:=bis;
  wertDerMitte:=aa[(von+bis) div 2]; //Die Mitte
  repeat
    while aa[i]<wertDerMitte do inc(i);
    while wertDerMitte<aa[j] do dec(j);
    if i<=j then Begin
      tausche(aa[i],aa[j]);
      inc(i);
      dec(j);
    End;
  until i>j;
  if von<j then sortieren(aa,von,j); //rekursiv
  if bis>i then sortieren(aa,i,bis);
end;


Leider fehlt hier jedoch noch die Definition der Prozedur "tausche". Ich habe schon zumindest das Gründgerüst für diese Prozedur geschrieben, aber Delphi meckert immer noch: Undefinierter Bezeichner tausche. Mein Grundgerüst lautet folgendermaßen:

Delphi-Quelltext
1:
2:
3:
4:
procedure tausche(arr1,arr2 : array of real);
begin

end;

Könnt ihr mir bei dieser Prozedur helfen? Ich weiß auch nicht, was innerhalb der Prozedur rein muss.

Moderiert von user profile iconGausi: Delphi-Tags hinzugefügt.


alzaimar - Mo 23.05.05 20:26

1. Prozedurkopf von 'tausche' ist falsch. Im Quicksort-Algorithmus wird 'tausche' mit zwei Real-Werten aufgerufen.
2. Man braucht doch zum Austauschen von zwei Werten keine Prozedur.

Der 'Ringtausch' ist eine der ersten 'Brainteaser', die angehende Informatiker lösen müssen. Der geht so:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
Procedure Ringtausch(Var a,b : Real);
Var
  h : Real;

Begin
  h := a; a := b; b := h
End;