Re: Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)
Hallo,
Zitat:
Delphi-Quellcode:
Gruß
function NatCompare(const Item1, Item2: WideString): Integer;
var Start1, Start2: Integer; S1, S2: WideString; N1, N2: Boolean; function IsDigit(const C: WideChar): Boolean; begin Result := (C in [WideChar('0')..WideChar('9')]); end; function GetNext(const S: WideString; var Start: Integer; var IsNumber: Boolean): WideString; var Len, Laenge, C: Integer; begin Len := Length(S); if Start > Len then begin Result := ''; Exit; end; // Beginnt eine Zahl? IsNumber := IsDigit(S[Start]); Laenge := 1; for C := Start + 1 to Len do begin // Weiterhin eine Zahl/ein Wort? if IsDigit(S[C]) = IsNumber then Inc(Laenge) else Break; end; Result := Copy(S, Start, Laenge); Inc(Start, Laenge); end; begin Result := 0; // Beide gleich -> Raus hier if Item1 = Item2 then Exit; Start1 := 1; Start2 := 1; // Alle Teile durchgehen repeat // Teile holen S1 := GetNext(Item1, Start1, N1); S2 := GetNext(Item2, Start2, N2); // Haben wir zwei Zahlen? if N1 and N2 then // Ja -> Zahlen Vergleichen Result := StrToInt(S1) - StrToInt(S2) else // Nein -> Normaler Stringvergleich Result := WideCompareStr(S1, S2); until (Result <> 0) or (Start1 > Length(Item1)) or (Start2 > Length(Item2)); end; xaromz |
Re: Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)
Zitat:
Optimal ist diese Sortierung natürlich auch nicht, schließlich kann man unter gewissen Umständen sogar in linearer Zeit Sortieren. Aber bleiben wir ruhig bei Merge- und Quicksort, die Laufzeiten sind hier einfach nur Asymptotisch angegeben, da ist doch ein wenig Relevantes versteckt (konst. Faktoren und mindest Länge). Ist deine Liste nur kurz genug, würde sich ein Bubblesort im Average-Case sogar besser machen als ein Quicksort. Ist die Liste nur Lang genug, wirst du auch nicht glücklich mit Quicksort, gerade bei sehr großen Datenmengen spielt Mergesort dann ein paar Vorteile aus (wenn er darauf optimiert wurde). Solange du aber Soriterungen im Speicher durchführst ist ohne frage Quicksort nicht langsam (in Kombination mit Bubblesort am schnellsten), aber ich denke mal es kommt doch eh nicht auf die paar ms mehr oder weniger an (gehe hier einfach mal von einer kleinen Liste < 10000 Elemente aus). Aber klar, hast recht, die konstanten Faktoren beim QS sind kleiner als die des MS. Gruß Der Unwissende |
Re: Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)
Mergesort im Speicher ist auch bei einigen Millionen Elementen *viel viel* langsamer als Quicksort. Probierts doch einfach aus. Theorie hin oder her, Quicksort, (eventuell iterativ), ist einfach am Schnellsten, auch wenn im 'worst case' Mergesort theoretisch(!) schneller ist.
Hier einige Ergebnisse:
Eine Anmerkung noch: Mergesort ist für Bänder entwickelt worden, für Speichermedien also, die nur sequentiell durchlaufen werden können. Dafür ist es aber als externes Sortierverfahren, wo die Elemente auf einer Festplatte liegen, ordendlich schnell. Der Speicherbedarf ist aber auch entsprechend. |
Re: Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)
Zitat:
soweit ich weiss ist 0(n*log(n)) doch besser als 0(n)...oder? einen Linear-sortierenden Algo kann ich dir auch schreiben ;) |
Re: Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)
Zitat:
Zitat:
Ich glaub, Du verwechselst da was. Es gibt natürlich Sortierverfahren, die linear sortieren, aber dazu musst Du Einschränkungen in Kauf nehmen. Du must spezielle Kentnisse über den Schlüssel verwenden (Zahl zwischen 1 und X oder so). Es ist schon bewiesen, das allgemeine Sortierverfahren im Optimum einen Aufwand von O(n log n) haben. Besser geht es einfach nicht. Jedenfalls nicht in diesem Universum. |
Re: Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)
Zitat:
Aber wie gesagt es sind starke Einschränkungen. Zitat:
Aber kann mich da auch total vertun (was mir dann zwar peinlich wäre, aber egal, man lernt ja gerne dazu!). Allerdings würde dass natürlich auch nur etwas mit Optimierung des Mergesorts, sehr großen Datenmengen und paralleler Verarbeitung bringen, sonst bleibt es Fakt, dass die Konstanten Faktoren des Mergesort größer sind als die des Quicksort. Aber wo ich mir auch noch recht sicher bin, bei sehr kleinen Mengen ist Bubblesort wiederum schneller als Quicksort. Wenn ich mich da an wirklich optimale (nicht nur bis auf konstante Faktoren) Sortieralgorithmen erinnere, werden nur Felder bestimmter Größe mit Quicksort sortiert. Ist ein Teilfeld erstmal klein genug, wird ein anderer verwendet (denke es war dort sogar Bubblesort). Egal, jedenfalls ist der Worst-Case gerade beim Quicksort einfach mal Theorie und die Rechnung des Average-Case anstrengend, wenn man nicht wirklich zig-Tausend oder millionen Einträge sortiert, denke ich wird man den Unterschied zwischen den beiden auch noch verkraften können (nicht immer!). Gruß Der Unwissende |
Re: Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)
Ok
dann werde ich bald den Beweis antreten, das ein sortieren in linearer Zeit möglich ist. aber erwartet nichts schnelles. All in All wird es trotzdem langsam sein...es geht ums prinzip ;) ich mach dann einen Thread auf wenns soweit ist^^ Also ich werde es zumindest versuchen ;) |
Re: Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)
Na dann wünsch ich dir mal viel Glück.
Wenn du lineare Zeit hast, dann ist das trotzdem schneller als jeder bekannte Sortieralgorithmus! Konstante Faktoren können beliebig groß werden, dass macht keinen Unterschied aus, ergo ist langsam hier falsch. Sagen wir du hast 1.000.000.000 * n Schritte zum Sortieren und sagen wir mal ganz einfach, Bubblesort braucht genau n^{2} Schritte. Dann würde das lineare Sortieren mit n > SQRT{1.000.000.000} schneller sein als Bubblesort. Wichtiger ist aber, dass du mit einer CPU die 1.000.000.000 mehr Operationen pro Zeit schafft, du einmal auch wirklich 1.000.000.000 mehr Elemente pro Zeit sortieren kannst, bei Bubblesort sind es aber nur SQRT{1.000.000.000} ^= 31.600 mehr Elemente. Darum geht es eigentlich, schnell oder langsam hängt irgendwo auch von der CPU ab, aber die ist nicht immer gleich. Wenn ich in 3 Sek. sortieren kann, was heißt das? Du weißt ja nicht womit ich wie sortiert habe. Ändert sich die CPU, ändert sich aber nichts an der Asymptotischen Betrachtung. Die Anzahl der Rechenschritte bleibt gleich. Gruß (und viel Glück beim Finden) Der Unwissende |
Re: Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)
Es ist vollbracht.
mein Algo kann Ganze Zahlen in linearer Zeit sortieren.
Delphi-Quellcode:
Mit anderen Typen als ganzen Zahlen...
procedure Sort(var A: TIntegerArray);
var Max,Min: Integer; H: TIntegerArray; i, j, k:Integer; begin Max:=A[0]; Min:=A[0]; for i:=0 to Length(A)-1 do begin if Max<A[i] then Max:=A[i]; if Min>A[i] then Min:=A[i]; end; SetLength(H,Max-Min+1); for i:=0 to Length(H)-1 do H[i]:=0; for i:=0 to Length(A)-1 do Inc(H[A[i]-Min]); k:=0; for i:=0 to Length(H)-1 do for j:=1 to H[i] do begin A[k]:=i+Min; Inc(k); end; end; Theoretisch ist es möglich. Praktisch ein ziemlicher aufwand^^ im Nachhinein habe ich rausgefunden das dieser Algo im Prinzip dem CountingSort entspricht. Quicksort ist tatsächlich der schnellste vergleichsbasierte algo. |
Re: Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)
Zitat:
Delphi-Quellcode:
Type
TIntegerArray = Array Of Integer; Var A : TIntegerArray; Begin SetLength (A,2); A[0] := 0; A[1] :=maxint; Sort (A); // <- peng End; Zitat:
Du machst, wie ich bereits sagte, starke Einschränkungen bezüglich des Schlüssels. Die Schlüssel sind abhängig vom vorhandenen Speicher, was nun wirklich nicht praktikabel ist. Die Laufzeit ist abhängig von der Verteilung der Schlüssel sowie von den Schlüsseln selbst. Wenn Du schon (annähernd) linear sortieren willst, dann wenigstens mit einem praktikablen Verfahren, als dem hier. Z.B. Bucketsort. Das geht aber auch nur mit Schlüsseln, die einigermaßen gleichmäßig verteilt sind. Im Übrigen ist Quicksort bei Arrays bis 2,5Mio Elementen immer noch wesentlich schneller. |
Alle Zeitangaben in WEZ +1. Es ist jetzt 18:24 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz