Entwickler-Ecke
Open Source Units - Fertiges Quicksort zum Record sortieren - STRG+C = FERTIG :)
mussterman - Mi 02.07.08 15:37
Titel: Fertiges Quicksort zum Record sortieren - STRG+C = FERTIG :)
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-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: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118:
| unit Unit2;
interface
uses 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 iLinks0:=low(aUn2SortDaten0); iRechts0:=high(aUn2SortDaten0); setlength(aSortVergleich,length(aUn2SortDaten0)); for i:=iLinks0 to iRechts0 do begin aSortVergleich[i]:=aUn2SortDaten0[i].sWort; end; quicksort_teil_a(aUn2SortDaten0, iLinks0, iRechts0); 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;
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;
function quicksort_teil_b(var aUn2SortDaten2: TMyArrayOne; iLinksP2,iRechtsP2:integer):integer; var iLinksTemp,iRechtsTemp:integer; begin iLinksTemp := iLinksP2; iRechtsTemp := iRechtsP2 - 1; repeat begin while ((aSortVergleich[iLinksTemp] <= aSortVergleich[iRechtsP2]) and (iLinksTemp < iRechtsP2)) do iLinksTemp:= iLinksTemp + 1; 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); quicksort_teil_c(aUn2SortDaten2, iLinksTemp, iRechtsP2); result:=iLinksTemp; end;
procedure quicksort_teil_c(var aUn2SortDaten3: TMyArrayOne; iDatensatzzeiger1, iDatensatzzeiger2: integer); var vHelp:Variant; iTempDatensatzanzahl:integer; begin vHelp:=aSortVergleich[iDatensatzzeiger1]; aSortVergleich[iDatensatzzeiger1]:=aSortVergleich[iDatensatzzeiger2];; aSortVergleich[iDatensatzzeiger2]:=vHelp; iTempDatensatzanzahl:=length(aUn2SortDaten3); setlength(aUn2SortDaten3,iTempDatensatzanzahl+1); aUn2SortDaten3[iTempDatensatzanzahl]:=aUn2SortDaten3[iDatensatzzeiger1]; aUn2SortDaten3[iDatensatzzeiger1]:=aUn2SortDaten3[iDatensatzzeiger2]; aUn2SortDaten3[iDatensatzzeiger2]:=aUn2SortDaten3[iTempDatensatzanzahl]; setlength(aUn2SortDaten3,iTempDatensatzanzahl); end;
end. |
Noch ein Beispiel für die Deklaration im anderen Unit
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
| 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
Delphi-Quelltext
1:
| 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 ...
Hidden - Mi 02.07.08 15:58
Hi,
Mach das doch etwas dynamischer, dass man nichtmehr die eingebundene Unit abändern muss: Du deklarierst eine Klasse mit der Property 'SortNr', nach der du sortierst.
Statt eines records leitet man dann eine Klasse davon ab und deklariert 'SortNr' z.B. als property SortNr read IrgendeineVariable;.
Propertys kann man doch durch einfache Redefinition umdeklarieren :gruebel: . Übergeben wird deiner Methode 'Sort' dann z.B. ein "Array of 'TQuicksortClass'". andere Eingenschaften wie z.B. 'Name', die in der abgeleiteten Klasse deklariert wurden, werden automatisch mitsortiert.
Btw: 'Sort' ist so häufig - nenn die Methode doch 'Quicksort', steckt auch mehr Information drin.
Btw2: Gibt es da noch nichts in der Library?
mfG,
Kha - Mi 02.07.08 16:05
Hidden hat folgendes geschrieben: |
Du deklarierst eine Klasse mit der Property 'SortNr', nach der du sortierst. |
Und welchen Typ soll diese Property haben? Da finde ich den Ansatz von TList.Sort (Vergleichsfunktion als Argument => Higher-Order Function) um Einiges dynamischer als eure beiden Vorschläge.
mussterman - Mi 02.07.08 16:07
Vielen Dank für den schönen Ratschlag und alle die noch kommen werden. Ich wollte sowas auch mal versuchen, aber das wollte ne so wie ich wollte. Aber ich würde mich freuen, wenn ihr den Code noch verfeinert, ich lerne gern noch was dazu ...
SilentDeath86 - Mi 20.05.09 10:35
Hallo. Erstmal danke für den Algorithmus. Allerdings funktioniert er bei mir nicht. Ich habe ein Array der Größe 10, welches aus einem Record besteht. Das Recors enthällt u.a. einen Real-Wert, nach dem sortiert werden soll. Nach der Sortierung ist das Array immer genauso wie vorher. Was mich wundert: In deiner Procedure "procedure quicksort_teil_c" wird zwar ein Array aUn2SortDaten3 aufgebaut/sortiert, aber mit diesem wird dann im weiteren Programm ja nicht weitergearbeitet, oder hab ich da was übersehen?
BenBE - Sa 23.05.09 11:55
Quicksort ist im Worst Case genauso langsam wie Bubble Sort. MergeSort ist schnell ;-) Unabhängig von der Eingabe :mrgreen:
@Titel: Könntest Du bitte die Aufforderung zu Copy Pasta weglassen? Die ist hier im Forum ungern gesehen! :mahn:
Gausi - Sa 23.05.09 13:57
Dafür braucht Mergesort aber normalerweise* doppelt soviel Speicher, da beim Mergen ein zweites Array gleicher Größe verwendet wird. Als Alternative wäre dann Heapsort zu nennen - im Worst-Case ebenfalls N*log(N), und das läuft auch auf konstantem Platz.
Außerdem kommt es in der Praxis nicht so sehr auf die theoretische Laufzeitkomplexität an - und Quicksort hat sich in den meisten Fällen als der Beste erwiesen.
______________________
Man kann zwar auch zwei Folgen ohne weiteren Speicherbedarf mischen, aber das möchte ich hier nicht weiter ausführen. ;-)
alzaimar - Sa 23.05.09 16:30
BenBE hat folgendes geschrieben : |
Quicksort ist im Worst Case genauso langsam wie Bubble Sort. MergeSort ist schnell ;-) Unabhängig von der Eingabe :mrgreen: |
Es gibt QS-Varianten, die das Pivot-Element zufällig auswählen. Somit gibt es praktisch keinen worst-case. Betonung auf 'praktisch'. Natürlich gibt es einen, aber der ist eben 'nicht' deterministisch. QS ist auch so schön kompakt, sodaß es eigentlich erste Wahl ist.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 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!