Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)?

**xaromz**

Hallo,

Zitat von Der_Ventilator:

Nur leider funktioniert sie überhaupt nicht.
Sie bewertet immer noch '2' größer als '14'.

Wenn Du meinem Link folgtest, würdest Du am Ende der Seite ein Archiv finden, in dem eine funktionierende Funktion steckt. Aber für Dich füge ich sie hier mal ein:

zusammenfalten · markieren

Delphi-Quellcode:

			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;

Gruß
xaromz

**Der_Unwissende**

Zitat von Phoenix:

Im Worst-Case ja. Aber auch nur da, und versuch Du mal Daten zu konstruieren die beim Quicksort zum Worst Case führen.
Vor allem, wenn man einen geschickten randomisierten Quicksort verwendet erhält man nachweislich nie den Worst-Case.

Will heissen wir ziehen hier zum Vergleich sowieso immer nur den Average-Case heran und der ist beim Quicksort mit O(n*log(n)) nunmal nachweislich am Optimum. Deswegen heisst das Ding ja auch quicksort: Weil es der schnellste zur Zeit bekannte Sortieralgorithmus ist.

Ich glaube jetzt hast du etwas zu stark pauschalisiert. Natürlich gibt es auch einen Worst-Case der erreicht werden kann, auch mit Randomisierung (gerade wenn es echt zufällig ist), aber die Wahrscheinlichkeit geht sehr sehr stark gegen 0.
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

**alzaimar**

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:

Testarray mit 500000 String-Elementen (random)
Iteratives Quicksort : 1762 ms
RekursivesQuicksort : 1923 ms
Mergesort : 4487 ms
Heapsort : 4716 ms

Testarray mit 1000000 Integer-Elementen (random)
Vergleich beginnt
Iteratives Quicksort : 350 ms
RekursivesQuicksort : 291 ms
Mergesort : 1152 ms
Heapsort : 1201 ms

Testarray mit 1000000 Intger-Elementen aufsteigend
Vergleich beginnt
Iteratives Quicksort : 150 ms
RekursivesQuicksort : 200 ms
Mergesort : 932 ms
Heapsort : 891 ms

Testarray mit 1000000 Integer-Elementen absteigend
Vergleich beginnt
Iteratives Quicksort : 170 ms
RekursivesQuicksort : 100 ms
Mergesort : 952 ms
Heapsort : 891 ms

Wie war das mit dem worst-case von Quicksort vs. Mergesort?

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.

**glkgereon**

Zitat von Der_Unwissende:

Optimal ist diese Sortierung natürlich auch nicht, schließlich kann man unter gewissen Umständen sogar in linearer Zeit Sortieren.

Hmm... Mit Quicksort oder wie?

soweit ich weiss ist 0(n*log(n)) doch besser als 0(n)...oder?

einen Linear-sortierenden Algo kann ich dir auch schreiben

**alzaimar**

Zitat von glkgereon:

soweit ich weiss ist 0(n*log(n)) doch besser als 0(n)...oder?

Äh. Nein. log(n)>1 für n>e. Ergo ist n*log(n)>n für alle n>e (2.7 sonstwas)

Zitat von glkgereon:

einen Linear-sortierenden Algo kann ich dir auch schreiben

Äh. Her damit und Du bekommst einen Nobelpreis. Und wirst Weltpräsident. Und erhälst das halbe Königreich. Und die Prinzessin oben drauf.
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.

**Der_Unwissende**

Zitat von alzaimar:

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.

Ja, wie gesagt mit starken Einschränkungen kann man linear Sortieren. Für Counting und Radixsort sollte dass sicherlich die Beschränkheit der Schlüssel sein (auch sollte X nicht zu groß sein, auch Speicher muss nicht verschwendet werden). Eine andere Möglichkeit besteht im Bucketsort, da muss ich "nur" Schlüssel gleichverteilt im Interval [quote=alzaimar]st auch der Linear.
Aber wie gesagt es sind starke Einschränkungen.

Zitat von alzaimar:

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.

Ich dachte eigentlich in Erinnerung zu haben, dass man durch dass geschickte Teilen beim Mergesort und genügend Elementen schneller werden kann als mit dem Quicksort. Lag dann daran, dass die gesamte Sortierung immer im schnellen Hauptspeicher stattfinden kann und ich die Teilfelder sogar Parallel sortieren könnte. Da ich beim Quicksort immer alle Elemente mit dem Pivotelement vergleichen muss, geht dass dort nicht (schlechter / weniger effizient).

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

**glkgereon**

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

**Der_Unwissende**

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

**glkgereon**

Es ist vollbracht.

mein Algo kann Ganze Zahlen in linearer Zeit sortieren.

zusammenfalten · markieren

Delphi-Quellcode:

			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;

Mit anderen Typen als ganzen Zahlen...
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.

**alzaimar**

Zitat von glkgereon:

mein Algo kann Ganze Zahlen in linearer Zeit sortieren.

Klappt nicht.

zusammenfalten · markieren

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 von glkgereon:

Mit anderen Typen als ganzen Zahlen... Theoretisch ist es möglich.

Praktisch wohl kaum.

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.