Fertiges Quicksort zum Record sortieren - STRG+C = FERTIG :)

[mussterman]

Quicksort ist mit eine der schnellsten Arten Daten zu sortieren.
Diese wurde nach dem Pseudocode von Wikipedia geschrieben.
Dieser Code ist in der Lage einen Array of Records (Tabelle) oder Arrays (Matrix) zu sortieren.
Es kann wahlweise von a..z oder von z..a sortiert werden.
An zwei Stellen muss man sich den Code anpassen, dies wurde aber beschrieben im Code.

Ich wünsche euch viel Spaß damit
MFG
mussterman

Delphi-Quellcode:

unit Unit2;

// INFO QuickSort zum Sortieren eines Array of Records oder Arrays
// INFO bzw. zum Sortieren einer "Tabelle"/"Matrix" nach einer Spalte
// INFO Aufruf erfolg mit quicksort(ARRAYbezeichung,Sortierrichtung)
// INFO Bei TRUE wird aufsteigend a..z und bei FALSE absteigend z..a sortiert

// VORRAUSSETZUNG es muss einen Datentyp vom Typ 'TMyArrayOne' geben !
// VORRAUSSETZUNG dieser kann ein "ARRAY of Records" oder "ARRAY of ARRAYs of 'DatentypXY'" sein

// VORRAUSSETZUNG ES MÜSSEN ZWEI STELLEN IM CODE ANGEPASST WERDEN, DIESE BEREICHE SIND DURCH --> GEKENNZEICHENT
// VORRAUSSETZUNG Das ist zueinem die Angabe der Spalte, nach der sortiert werden soll.
// VORRAUSSETZUNG Und zum anderen die Verknüpfung mit der Unit wo der Datentyp 'TMyArrayOne' deklariert wurde
interface

uses
    // --> Wo ist Datentyp 'TMyArrayOne' deklariert ???
    Unit1;

var aSortVergleich: array of Variant;
    procedure quicksort(var aUn2SortDaten0: TMyArrayOne; bSortierrichtung0:boolean);
    procedure quicksort_teil_a(var aUn2SortDaten1: TMyArrayOne; iLinksP1,iRechtsP1:integer);
    function  quicksort_teil_b(var aUn2SortDaten2: TMyArrayOne; iLinksP2,iRechtsP2:integer):integer;
    procedure quicksort_teil_c(var aUn2SortDaten3: TMyArrayOne; iDatensatzzeiger1, iDatensatzzeiger2: integer);

implementation

procedure quicksort(var aUn2SortDaten0: TMyArrayOne; bSortierrichtung0:boolean);
var iLinks0,iRechts0,i,j:integer;
begin
  // Der erste Datensatz LINKS im Array ist auf Position X
  iLinks0:=low(aUn2SortDaten0);
  // Der letze Datensatz RECHTS im Array ist auf Position Y
  iRechts0:=high(aUn2SortDaten0);
  // Aufbau des Vergleichsarrays
  setlength(aSortVergleich,length(aUn2SortDaten0));
  for i:=iLinks0 to iRechts0 do
    begin
  // ********************************************************* //
  // ** --> Angabe nach welcher Spalte sortiert werden soll ** //
      aSortVergleich[i]:=aUn2SortDaten0[i].sWort;
  // ********************************************************* //
    end;
    
  // ===========================================================
  // * BEGINN DER SORTIERUNG - KEINE ÄNDERUNGEN MEHR NOTWENDIG *

  //Durchführen der Sortierung
  quicksort_teil_a(aUn2SortDaten0, iLinks0, iRechts0);
  // es wurde jetzt von a..z sortiert, falls z..a gewünscht ist, geschieht das jetzt
  if not bSortierrichtung0 then
    begin
      repeat
        begin
          quicksort_teil_c(aUn2SortDaten0, iLinks0, iRechts0);
          iLinks0:=iLinks0+1;
          iRechts0:=iRechts0-1;
        end;
      until not (iLinks0 < iRechts0);
    end;
end;

// + Teilprozedure 1 von QuickSort +
procedure quicksort_teil_a(var aUn2SortDaten1: TMyArrayOne; iLinksP1,iRechtsP1:integer);
var iTeiler:integer;
begin
  if iLinksP1 < iRechtsP1 then
    begin
      iTeiler := quicksort_teil_b(aUn2SortDaten1, iLinksP1, iRechtsP1);
      quicksort_teil_a(aUn2SortDaten1, iLinksP1, iTeiler-1);
      quicksort_teil_a(aUn2SortDaten1, iTeiler+1, iRechtsP1);
    end;
end;

// + Teilprozedure 2 von QuickSort +
function quicksort_teil_b(var aUn2SortDaten2: TMyArrayOne; iLinksP2,iRechtsP2:integer):integer;
var iLinksTemp,iRechtsTemp:integer;
begin
     iLinksTemp := iLinksP2;
     // Starte mit j links vom Pivotelement
     iRechtsTemp := iRechtsP2 - 1;
     repeat
      begin
        // Suche von links ein Element, welches größer oder gleich dem Pivotelement ist
        while ((aSortVergleich[iLinksTemp] <= aSortVergleich[iRechtsP2]) and (iLinksTemp < iRechtsP2)) do  iLinksTemp:= iLinksTemp + 1;
        // Suche von rechts ein Element, welches kleiner oder gleich dem Pivotelement ist
        while ((aSortVergleich[iRechtsTemp] >= aSortVergleich[iRechtsP2]) and (iRechtsTemp > iLinksP2)) do iRechtsTemp:= iRechtsTemp - 1;
        if iLinksTemp < iRechtsTemp then quicksort_teil_c(aUn2SortDaten2, iLinksTemp, iRechtsTemp);
      end;
     until not(iLinksTemp < iRechtsTemp); // solange iLinks an iRechts nicht vorbeigelaufen ist
     // Tausche Pivotelement (daten[rechts]) mit neuer endgültigen Position (daten[i])
     quicksort_teil_c(aUn2SortDaten2, iLinksTemp, iRechtsP2);
     // gib die Position des Pivotelements zurück
     result:=iLinksTemp;
end;

// + Teilprozedure 3 von QuickSort +
procedure quicksort_teil_c(var aUn2SortDaten3: TMyArrayOne; iDatensatzzeiger1, iDatensatzzeiger2: integer);
var vHelp:Variant;
    iTempDatensatzanzahl:integer;
begin
  // Tauschen der beiden Vergleichswerte
  vHelp:=aSortVergleich[iDatensatzzeiger1];
  aSortVergleich[iDatensatzzeiger1]:=aSortVergleich[iDatensatzzeiger2];;
  aSortVergleich[iDatensatzzeiger2]:=vHelp;
  // Tauschen von zwei Datensätzen
  iTempDatensatzanzahl:=length(aUn2SortDaten3);
  setlength(aUn2SortDaten3,iTempDatensatzanzahl+1);
  aUn2SortDaten3[iTempDatensatzanzahl]:=aUn2SortDaten3[iDatensatzzeiger1];
  aUn2SortDaten3[iDatensatzzeiger1]:=aUn2SortDaten3[iDatensatzzeiger2];
  aUn2SortDaten3[iDatensatzzeiger2]:=aUn2SortDaten3[iTempDatensatzanzahl];
  setlength(aUn2SortDaten3,iTempDatensatzanzahl);
end;

// * ENDE VON QUICKSORT * //
//====================================================

end.

Noch ein Beispiel für die Deklaration im anderen Unit

Delphi-Quellcode:

type
  TMyRecordOne = record
    iZahl:integer;
    sWort:string;
    bEigenschaft:boolean;
  end;
  TMyArrayOne = array of TMyRecordOne;

var
  aDatenbank: TMyArrayOne;

Und der Aufruf der Sortierung dann im Code
quicksort(aDatenbank,True);
Weis jemand zufällig, wie man im Record ein Feld mit seiner Bezeichnung oder einer Nummer ansprechen kann? Es soll den Sinn haben, dass man bei Aufruf von Quicksort übergibt, nach was sortiert werden soll. Diese Wert ist ja entweder ein String oder eine Nummer. Wenn jemand eine Möglichkeit kennt, dann schreibt sie - ich setze sie dann gleich mit um ...

[Missionar]

Zitat von mussterman:

Quicksort ist mit die schnellste Art Daten zu sortieren.

Diese Aussage ist nicht zutreffend.

Ausserdem gibt es für QSort eine Funktion in der Libary. Weshalb sollte dieser CodeLib Eintrag gebraucht werden?

[brechi]

Zitat von Missionar:

Zitat von mussterman:

Quicksort ist mit die schnellste Art Daten zu sortieren.

Diese Aussage ist nicht zutreffend.

Wenn er geschrieben hätte, es wäre die schnellste Art Daten zu sortieren, könnte man ja noch drüber streiten. Aber im Durchschnitt hat QSort nen Laufzeitverhalten von n log(n) und gehört somit zu den schnellsten Sortierverfahren (und ist in der Regel auch das schnellste).

[Laufi]

Hallo!

Also wenn man genug speicher hat kann man auch einen algorithmus der in der linearen zeit sortiert man muss einfach den schlüssel als index nehmen

Liebe grüsse
Laufi

[Namenloser]

@mussterman
Nix für ungut - aber eine TList find ich da praktischer

[Delphi-Laie]

Zitat von Laufi:

Also wenn man genug speicher hat kann man auch einen algorithmus der in der linearen zeit sortiert man muss einfach den schlüssel als index nehmen

Schön. Das funktioniert aber nur mit integren Sortierelementen bzw. Elementeschlüsseln. Doch was passiert, wenn die Sortierelemente nicht nur aus Schlüsseln bestehen (bzw. nicht mit ihren Schlüsseln identisch sind), mit dem (oft viel größeren, mehr Informationen beinhaltenden) „Rest“ (in dieser Diskussion sind solche „komplexen“ Elemente beispielhaft Records)? Der geht nämlich verloren!

Solche Sortieralgorithmen werden eben nicht umsonst als „speziell“ tituliert, denn sind nunmal nicht allgemein, d.h. für alle Elemente-/Schlüsselarten /-typen anwendbar.

[alzaimar]

Zitat von Laufi:

Also wenn man genug speicher hat kann man auch einen algorithmus der in der linearen zeit sortiert man muss einfach den schlüssel als index nehmen

Das stimmt. Einfach den kleinsten und größten Schlüssel nehmen, ein Array dazwischen aufspannen, befüllen, auslesen, fertig.
Klar.
Und so kann man auch ein ARRAY OF STRING glasklar in linearer Zeit sortieren. Logisch.

Oder, sagen wir ein ARRAY OF INTEGER mit drei Werten (wir machenes kompliziert) : (maxint, -maxint, 0). Auch klar. Nur. Mit dem RAM ist das so eine Sache. Er ist, wie soll ich mich ausdrücken... endlich. Begrenzt. Äh. Limitiert.. Und so. Ne.

Delphi-Laie hat schon Recht, wenn er sagt, das diese Form der Sortierung zu speziell ist und daher i.a. nicht zu gebrauchen.