Autor |
Beitrag |
mussterman
Hält's aus hier
Beiträge: 2
|
Verfasst: Mi 02.07.08 15:37
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
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 ...
Zuletzt bearbeitet von mussterman am Mo 07.07.08 16:14, insgesamt 2-mal bearbeitet
|
|
Hidden
Beiträge: 2242
Erhaltene Danke: 55
Win10
VS Code, Delphi 2010 Prof.
|
Verfasst: 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 . Ü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,
_________________ Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)
|
|
Kha
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: 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
Hält's aus hier
Beiträge: 2
|
Verfasst: 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
Hält's aus hier
Beiträge: 2
|
Verfasst: 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?
|
|
ffgorcky
Beiträge: 573
WIN XP/2000 & 7Prof (Familie:Win95,Win98)
|
Verfasst: Sa 23.05.09 09:03
SilentDeath86 hat zu den Thema hier noch einmal einen einzelnen Beitrag gemacht, wo er auf diesen hier verweist.
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Sa 23.05.09 11:55
Quicksort ist im Worst Case genauso langsam wie Bubble Sort. MergeSort ist schnell Unabhängig von der Eingabe
@Titel: Könntest Du bitte die Aufforderung zu Copy Pasta weglassen? Die ist hier im Forum ungern gesehen!
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Gausi
Beiträge: 8538
Erhaltene Danke: 475
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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.
_________________ We are, we were and will not be.
|
|
alzaimar
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: Sa 23.05.09 16:30
_________________ Na denn, dann. Bis dann, denn.
|
|
|