Ich bitte um Erklärung eines Quellcodes

[Tabriel]

Also ich bin es nochmal mit mienem Delphi Projekt QuickSort implementieren. Ich hatte ja bereits in einem anderen Thread einmal gepostet und wollte euch hier nochmal dafür danken aber ich bin jetzt auch noch dummer weise auf ein neues Problem gestoßen udn zwar habe ich tatsächlich einen Algorithmus gefunden der mein Problem behebt, auch wenn ich zu meiner Schande gestehen muss das ich es nicht selbst hin bekommen habe allerdings war das die einzige Lösung, weil durch die Tatsache das das ein Schulprojekt ist, die Zeit doch sehr drängt.

Das Problem ist folgendes mir sind einige der Begriffe und Aufrufe die hier verwendet werden einfach in keiner Art und weise ein Begriff wenn ihr mir also eventuell kurz die Funktion des Quellcodes erläutern könntet den ich poste wäre ich unglaublich dankbar

Also der Quellcode den ich gefunden habe um eine Liste zu Sortieren und gleichzeitig Vergleiche und Swaps zu zählen sieht wie folgt aus:

Delphi-Quellcode:

Procedure TWortListe quick;
begin
  Vergleiche :=0;
  Swaps :=0;
  PegelStart(round(Listenlaenge*log2(Listenlaenge)));             //Dies PegelStart ist das nur eine Variabele oder was anderes? und warum log2?
  quicksort(1,Listenlaenge,vergleiche,swaps);                     //mit dem Aufruf Quicksort habe ich allgemein verständnisprobleme
end;

Procedure TWortListe.Quicksort(anfang,ende: Cardinal;var act, sw : Cardinal);
var linkerzeiger, rechterzeiger : Cardinal;
    mitte  : string;

begin

 linkerzeiger    :=  anfang;
  rechterzeiger  :=  ende;
  mitte          :=  Kollektion[(linkerzeiger+rechterzeiger)div2];
  Pegel.Position :=  Vergleiche;                                     //Hier taucht der Pegel nochmal auf  :?: 

while(Kollektion[linkerzeiger]<mitte) do
begin
  linkerzeiger  := linkerzeiger+1;
  inc(act);                                                            //Was ist act :(
end;


while(Kollektion[rechterzeiger]>mitte) do
begin
  rechterzeiger  := rechterzeiger-1;
  inc(act);                                                             //Hier habe ich nochmal das selbe Problem 
end;

if linkerzeiger <= rechterzeiger
then
  begin
    Tauschen(Kollektion[linkerzeiger],Kollektion[rechterzeiger]);
    linkerzeiger := linkerzeiger + 1;
    rechterzeiger := rechterzeiger - 1;
    inc(Swaps);
    inc(act);                                                            
  end; (*if*)
until rechterzeiger < linkerzeiger; 
 

if anfang < rechterzeiger
  then quicksort(anfang, rechterzeiger, Vergleiche, swaps);                    //Hier habe ich wieder ein PRoblem mit dem Aufruf Quciksort
  if linkerzeiger < ende
  then quicksort(linkerzeiger,ende,Vergleiche,swaps);                           //Hier auch und ich ahb das in den Klammer nicht verstanden
end; (*quicksort*)

Also das ist mien Problem um das es sich handelt allerdings könnte natürlich jetzt das Problem auftauchen das ihr wiel ihr nur ienen Ausschnitt des Algorithmus zur verfügung habt, ihr nicth völlig verstehen könnt was das jetzt alles zu bedeuten hat aber ich vertraue auf euer Delphi wissen, dass ihr mir helfen könnt das wäre echt super genial.

Ich entschuldige mich auch für die teilweise eventuell dummen Fragen aber ich ibn einfach in keiner art und weise in der Thematik wirklich dirn bzw nicht oder noch nicth in der Lage einen solchen Algorithmus zu programmieren.

Ich danke euch jetzt schonmal für eure Mühen!!!

mfg Tabriel

[edit=mkinzler]Delphi-Tag eingefügt Mfg, mkinzler[/edit]

[himitsu]

Quicksort
Wikipedia > Quicksort

also vorallem im letzen Links ist eine garnicht soooo dumme Erklärung des Verfahrens versteckt

[Tabriel]

Mein Problem ist nicht das ich das Verfahren nicht verstanden habe. Das Verfahren kenne ich mitlerweille recht gut, aber ich habe mit diesem speziellen Quellcode Probleme. Das ist mein Problem und da habe ich bei Wikipdia auch keine nennenswerte Lösung zu gefunden!!!

aber danke für den Link

mfg Tabriel

[quendolineDD]

Ohne den Quelltext angeschaut zu haben (kannst du deinen Ausgangspost nocheinmal editieren und den Quelltext in die DELPHI-Tags setzen. Dann ließt sich das alles einfacher). Welche Aufrufe und Befehle sind dir denn unklar? Hast du diese schon einmal markiert und mit F1 in der Hilfe nach deren Erläuterung geschaut?

Edit2:
Das in den Klammern hinter Quicksort ist einfach nur die Paramterliste. Und im Quelltext werden dorte die Paramter reingeschrieben...

[Cyf]

Reformatiert/korrigiert (kein Wunder, dass du ihn so nicht verstehtst):

Delphi-Quellcode:

Procedure TWortListe.Quick; //verbessert?
begin
  //ich denk mal die sind globale Zähler oder Felder, die hier zurückgesetzt werden
  Vergleiche :=0;
  Swaps :=0;
  //PegelStart ist eine Prozedur, deren Implementierung du nicht gepostet hast, siehe Anmerkung zu Pegel
  PegelStart(round(Listenlaenge*log2(Listenlaenge)));
  //erster Parameter: "untere" sortierte Grenze, zweiter: "obere" sortierte Grenze
  //die anderen zwei Parameter zählen wohl die Vergleiche und Tauschoperationen mit (starten hier mit 0)
  quicksort(1,Listenlaenge,vergleiche,swaps);
end;

Procedure TWortListe.Quicksort(anfang, ende: Cardinal; var act, sw : Cardinal);
var
  linkerzeiger, rechterzeiger : Cardinal; //imho recht sinnlose lokale Kopien der Parameter
  mitte : string;
begin
  linkerzeiger := anfang;
  rechterzeiger := ende;
  //auch wieder irgendwas mit ner Anzeige, die die Mitte, des Sortierbereichs zeigt?
  mitte := Kollektion[(linkerzeiger+rechterzeiger)div2];
  Pegel.Position := Vergleiche; //Hier taucht der Pegel nochmal auf - vielleicht eine Progessbar o.ä.?

  while(Kollektion[linkerzeiger]<mitte) do //warum zum Henker ein Stringvergleich?
  begin
    linkerzeiger := linkerzeiger+1;
    //Was ist act - Act ist ein var Parameter der Funktion - aus deinem oberen Aufruf raus zu schließen die Tauschanzahl
    inc(act);
  end;


  while(Kollektion[rechterzeiger]>mitte) do //siehe Schleife davor
  begin
    rechterzeiger := rechterzeiger-1;
    inc(act); //Hier habe ich nochmal das selbe Problem
  end;

  if linkerzeiger <= rechterzeiger then //joa, der restliche Quicksort halt
  begin
    //ahh weil du eine Art Stringliste sortierst, damit ist dann auch Mitte klar (Privotelement)
    Tauschen(Kollektion[linkerzeiger],Kollektion[rechterzeiger]);
    linkerzeiger := linkerzeiger + 1;
    rechterzeiger := rechterzeiger - 1;
    inc(Swaps);
    inc(act);
  end; (*if*)
until rechterzeiger < linkerzeiger; //kompiliert das, so ohne Repeat?


  if anfang < rechterzeiger then
    quicksort(anfang, rechterzeiger, Vergleiche, swaps); //Hier habe ich wieder ein PRoblem mit dem Aufruf Quciksort
  if linkerzeiger < ende then
    quicksort(linkerzeiger,ende,Vergleiche,swaps); //Klammer = deine Parameter beim Aufruf, wie oben halt

end; (*quicksort*)

Insgesamt viel

[Tabriel]

Wie oben ja auch erläutert habe hatte ich auch einige Probleme damit und wie gesagt habe ich es auch nciht selber geschrieben.

Aber ich danke dir für deinen ausführlichen Erklärungen also immerhin einigermaßen müsste das klappen wenn ich das Vorstellen soll. Ich danke dir für deine Mühen.

mfg Tabriel

[Satty67]

Zitat von Cyf:

Procedure TWortListe.Quicksort(anfang, ende: Cardinal; var act, sw : Cardinal);
var
linkerzeiger, rechterzeiger : Cardinal; //imho recht sinnlose lokale Kopien der Parameter

Nein, sind nicht sinnlos. Die lokalen Zeiger wandern durch den Ausschnitt der Liste ausgehend von Anfang und Ende. Anfang und Ende werden später auch noch mit ihrem Ausgangswert gebraucht um weitere Teillisten zu definieren.

[sx2008]

Beim Sortieren gibt es 2 Grundoperationen:
a.) Vergleichen zweier Elemente
b.) Vertauschen zweier Elemente
Dann wäre es doch logisch, wenn es in deinem Sourcecode zwei Methoden gibt:

Delphi-Quellcode:

function TWortListe.Compare(a,b:integer):integer;
begin
  Inc(compare_counter);
  ... // hier der Code zum Vergleichen
end;
Procedure TWortListe.Swap(a,b:integer);
begin
  Inc(swap_counter);
  ... // hier der Code zum Vertauschen
end;

Und dann ist ganz klar, dass nur noch Compare() und Swap() aufgerufen werden, anstatt diese Operationen
direkt im QSort Algo aufzurufen.

[Cyf]

Zitat von Satty67:

Zitat von Cyf:

Procedure TWortListe.Quicksort(anfang, ende: Cardinal; var act, sw : Cardinal);
var
linkerzeiger, rechterzeiger : Cardinal; //imho recht sinnlose lokale Kopien der Parameter

Nein, sind nicht sinnlos. Die lokalen Zeiger wandern durch den Ausschnitt der Liste ausgehend von Anfang und Ende. Anfang und Ende werden später auch noch mit ihrem Ausgangswert gebraucht um weitere Teillisten zu definieren.

Ohh... Überzeugt
Hab nach dem komischen Repeat etwas aufgehört mitzudenken.

[Hybrid666]

Delphi-Quellcode:

  //auch wieder irgendwas mit ner Anzeige, die die Mitte, des Sortierbereichs zeigt?
  mitte := Kollektion[(linkerzeiger+rechterzeiger)div2];

Hi erstmal, ich denk die mitte ist hier das Pivot Element (wollt ich nur gesagt haben weil du den kommentar als Frage gestellt hast).

Was ein Pivot Element ist bitte aus WP entnehmen.

Delphi-Quellcode:

  if anfang < rechterzeiger then
    quicksort(anfang, rechterzeiger, Vergleiche, swaps); //Hier habe ich wieder ein PRoblem mit dem Aufruf Quciksort

Das ist würde ich jetzt mal sagen der Rekursive aufruf um die erhaltenen Teillisten zu sortieren, oder täusche ich mich?

until rechterzeiger < linkerzeiger; //kompiliert das, so ohne Repeat? Würde mich fast etwas wundern, ist da evtl das repeat verlorgen gegangen? also theoretisch müsse es doch wohl gleich hinterm begin der prozedur hin, nicht oder?

  linkerzeiger, rechterzeiger : Cardinal; //imho recht sinnlose lokale Kopien der Parameter Nein, denke ich nicht, er nutzt sie zum inkrementieren und dekrementieren.

Hab noch meine Kommentare hinzugefügt:

Delphi-Quellcode:

Procedure TWortListe.Quick; //verbessert?
begin
  //ich denk mal die sind globale Zähler oder Felder, die hier zurückgesetzt werden
  Vergleiche :=0;
  Swaps :=0;
  //PegelStart ist eine Prozedur, deren Implementierung du nicht gepostet hast, siehe Anmerkung zu Pegel
  PegelStart(round(Listenlaenge*log2(Listenlaenge)));
  //erster Parameter: "untere" sortierte Grenze, zweiter: "obere" sortierte Grenze
  //die anderen zwei Parameter zählen wohl die Vergleiche und Tauschoperationen mit (starten hier mit 0)
  quicksort(1,Listenlaenge,vergleiche,swaps);
end;

Procedure TWortListe.Quicksort(anfang, ende: Cardinal; var act, sw : Cardinal);
var
  linkerzeiger, rechterzeiger : Cardinal; //imho recht sinnlose lokale Kopien der Parameter
                                          //Hybrid666: Denke ich nicht, werden im quelltext inkrementiert und dekrementiert
                                          //           Die werte anfang und ende werden auch wieder verwendet (sollen also nicht
                                          //           verändert werden)
  mitte : string;
begin
  linkerzeiger := anfang;
  rechterzeiger := ende;
  //auch wieder irgendwas mit ner Anzeige, die die Mitte, des Sortierbereichs zeigt?
  //Hybrid666: Pivot-Element (siehe Wikipedia)
  mitte := Kollektion[(linkerzeiger+rechterzeiger)div2];
  Pegel.Position := Vergleiche; //Hier taucht der Pegel nochmal auf - vielleicht eine Progessbar o.ä.?
                                // Hybrid666: Denke auch, auf jedenfall wirds ne ausgabe sein, wieviele vergleiche gemacht wurden

  while(Kollektion[linkerzeiger]<mitte) do //warum zum Henker ein Stringvergleich?
                                           //Hybrid666: SUchen nach einem Element was auf die andere hälfte der
                                           //           liste soll
  begin
    linkerzeiger := linkerzeiger+1;
    //Was ist act - Act ist ein var Parameter der Funktion - aus deinem oberen Aufruf raus zu schließen die Tauschanzahl
    inc(act);
  end;


  while(Kollektion[rechterzeiger]>mitte) do //siehe Schleife davor
                                            //Hybrid666: Tauschpartner im rechten teil für linken teil suchen
  begin
    rechterzeiger := rechterzeiger-1;
    inc(act); //Hier habe ich nochmal das selbe Problem
  end;

  if linkerzeiger <= rechterzeiger then //joa, der restliche Quicksort halt
  begin
    //ahh weil du eine Art Stringliste sortierst, damit ist dann auch Mitte klar (Privotelement)
    Tauschen(Kollektion[linkerzeiger],Kollektion[rechterzeiger]);
    linkerzeiger := linkerzeiger + 1;
    rechterzeiger := rechterzeiger - 1;
    inc(Swaps);
    inc(act);
  end; (*if*)
until rechterzeiger < linkerzeiger; //kompiliert das, so ohne Repeat?


  if anfang < rechterzeiger then
    quicksort(anfang, rechterzeiger, Vergleiche, swaps); //Hier habe ich wieder ein PRoblem mit dem Aufruf Quciksort
                                                         //Hybrid666: Rekursiver aufruf um die 2 erhaltenen Teillisten zu sortieren (hier die eine seite)
  if linkerzeiger < ende then
    quicksort(linkerzeiger,ende,Vergleiche,swaps); //Klammer = deine Parameter beim Aufruf, wie oben halt
                                                   //Hybrid666: Hier der aufruf für die andere seite

end; (*quicksort*)

MfG