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

[Der_Ventilator]

Hi, ich möchte einige Strings in eine logisch richtige Reihenfolge bringen (das das der Explorer ab WinXP auch macht).

Also nicht

bla-1-bla
bla-2-bla
bla-21-bla
bla-3-bla

(was ein 'normaler' Sortieralgorithmus, wie z.B. Quicksort, machen würde),

sondern

bla-1-bla
bla-2-bla
bla-3-bla
bla-21-bla

Im Grunde läuft alles darauf hinaus, nicht die < und > Vergleichsoperatoren von Delphi zu verwenden, sondern eine eigene isLower( , ):boolean Funktion zu schreiben.

Hab mir das so gedacht:

Haben die Strings 200 Zeichen, dann erstelle ich mir ein int-Array mit 200 Spalten und belege jede Zelle mit dem Ord( ) Wert der einzelnen Buchstaben des Strings und bei Zahlen (wenn mehrere Ziffern hintereinander stehen, zusammenfassen!) werden diese direkt hineingeschrieben; dann erfolgt solange Spaltenweise der Vergleich, bis ein Unterschied festzustellen ist.
Sind meine Überlegungen richtig bzw. hat schon eine solche Stringvergleichsprozedur geschrieben (die evtl schneller als meine ist)?

[tomsel]

Wie wäre es, den numerischen Teil vom Rest des Strings irgendwie zu trennen und nur, wenn bei der Zahl Gleichheit besteht, den Reststring zum Vergleich mit < > heranzuziehen?

[Der_Ventilator]

Das Problem ist, das die Strings nicht ganz so gleichförmig sind, wie ich es dargestellt habe:

Es geht um einen Mp3-Player, der Albumname + Tracknummer + Songtitel in einer Zeile ausgibt (id3 tag).

Nun sind ja die nichtnumerischen Teile nicht immer gleich lang (verschiedene Bandnamen usw). Deshalb müsse ich mir bei der Trennung dann noch zusätzlich die Position merken, wo die Zahlen ursprünglich waren, was ich mit meinen Spaltenindizes machen möchte.

[leddl]

Dann würde ich an deiner Stelle einfach den numerischen Teil aus den Strings auslesen und dann danach sortieren.

[Der_Ventilator]

Ich erstelle zur Zeit erst ein Liste aller Einträge.
Diese wird dann per Quicksort sortiert.
Nun sind da aber schon alle verschiedenen Alben bzw Bandnamen verarbeitet.
Wenn ich jetzt nur nach Nummern sortiere, reise ich mir doch die Alben auseinander.

Ich suche einfach eine schnelle Funktion, die 2 Strings nach oben genanneter Logik vergleicht.
Evtl. eine, die sogar ein 'Ü' als 'U' interpretiert.

[Der_Unwissende]

Hi,
benutz einfach ein wenig topologisches Sortieren (hoffe ich vertue mich da nicht mit dem Namen, die liegen schon zurück).
Pack einfach alle Tracks eines Albums (oder Interpreten oder was auch immer du als primäres Sortierkriterium hast) in je eine Liste ein.
Diese Liste Sortierst du dann nach dem sekundären Sortierkriterium (hier also die Tracknummer), dann bekommst du also sowas wie
1.
Album1-1 -> Album1-10 -> Album1-2...
Album2-1 -> Album2-10 -> Album2-2...
...
2.
Album1-1 -> Album1-2 -> Album1-10....
Album2-1 -> Album2-2 -> Album2-10....

Jetzt weißt du das die Listen jeweils richtig sortiert sind und muss nur noch in der Reihenfolge der Listen einfügen.

Gruß Der Unwissende

[leddl]

:gruebel: Meinst du vielleicht ein "stabiles" Sortierverfahren? :zwinker:
MergeSort wäre zB ne Möglichkeit. Das hat im übrigen auch bei großen Datenmengen ne bessere Laufzeit als dein Quicksort. Das hat nämlich im worst Case O(n²), MergeSort nur O(n*logn).

[alzaimar]

Grundsätzlich musst Du einfach nur eine Ordnung auf die Titel definieren. Das erreichst Du mit einer Funktion 'CompareTitle (a,b)', das für zwei Titel a und b einen Wert liefert, der angibt, ob a nun vor b, danach oder identisch mit b ist.

Das Sortierverfahren dürfte hier keine grosse Rolle spielen, denn ob nun Merge-, Quick-, Bubble-, Heap-, Shaker- oder was weiss ich was-Sort, Alle Verfahren bauen auf der o.g. Funktion auf.

Der 'topologische' Ansatz ist zwar vom Gedankengang richtig klassifiziert, aber topologisches Sortieren basiert auf Graphen, wobei ich nicht vorschlage, die Titelliste in einen Graphen zu übertragen. Es wäre wohl eher eine Unterteilung in Ebenen. Also, erst alle Titel in Albem unterteilen und dann jedes Album getrennt 'heuristisch-numerisch' sortieren. Anschließend die Alben noch (z.B. alphabetisch) sortieren. Vielleicht die Alben wieder in Genres und Musikstile unterteilen und dann sortieren etc.

Das *kann* man durchaus mit einem Sortiervorgang machen. Dazu musst du aber wissen, wo der Albentitel im String steckt. Hier mal ein ziemlich abstrakter Pseudocode für die zentrale Vergleichsfunktion:

Delphi-Quellcode:

Function CompareTitle (TitleA, TitleB : String) : Integer;
Var
  AlbumA, AlbumB : String;

Begin
  Result := CompareText (ExtractAlbumFromTitle (TitleA), ExtractAlbumFromTitle (TitleB));
  If Result<>0 Then Exit;
// Beide Titel sind vom selben Album
  Result := CompareText (ExtractSongNumberFromTitle (TitleA), ExtractSongNumberFromTitle (TitleB));
End;

Dann kannst Du alle Titel in eine Stringliste reinpacken und per CustomSort sortieren. Dieser Methode übergibst Du dann o.g. Funktion als Parameter. Ob die genauso aussehen muss, weiss ich nicht, aber wozu gibts die Online-Hilfe.

[leddl]

Zitat:

Zitat von alzaimar

Das Sortierverfahren dürfte hier keine grosse Rolle spielen, denn ob nun Merge-, Quick-, Bubble-, Heap-, Shaker- oder was weiss ich was-Sort, Alle Verfahren bauen auf der o.g. Funktion auf.

:shock: Also den Unterschied von QuickSort zu MergeSort merkst du bei entsprechend großen Datenmengen sehr wohl. Die Frage ist eben, wieviele Titel er in seiner Liste hat :zwinker:

Zitat:

Zitat von alzaimar

Der 'topologische' Ansatz ist zwar vom Gedankengang richtig klassifiziert, [...]

Wie gesagt, ich denke, er meinte ein stabiles Sortierverfahren, so daß ein erneutes Sortieren nach einem anderen Kriterium die Reihenfolge früherer Sortierkriterien beibehält.

[alzaimar]

Zitat:

Zitat von leddl

:shock: Also den Unterschied von QuickSort zu MergeSort merkst du bei entsprechend großen Datenmengen sehr wohl. Die Frage ist eben, wieviele Titel er in seiner Liste hat :zwinker:

Nee, is klar. Ich wollte eher auf die Erwähnung von Quicksort und Mergesort eingehen.

Aber: Vergleiche mal die Quick- mit Mergesort, wenn die Daten sich auf (langsamen) Datenträgern befinden (File Of TMyRecord). *Dann* merkst Du den Unterschied. Das Ergebnis wird aber nicht das sein, was Du erwartest.
Übrigens ist laut der grauen Theorie Mergesort im Gegensatz zu Quicksort vom Laufzeitverhalten auch im Worst-Case-Bereich optimal. Davon merkt man beim In-Memory-sortieren zwar Nichts, aber beim externen Sortieren sehr wohl: Dafür wurde Mergesort (Stichwort: Bänder) auch entwickelt.

Zitat:

Zitat von leddl

Zitat:

Zitat von alzaimar

Der 'topologische' Ansatz ist zwar vom Gedankengang richtig klassifiziert, [...]

Wie gesagt, ich denke, er meinte ein stabiles Sortierverfahren, so daß ein erneutes Sortieren nach einem anderen Kriterium die Reihenfolge früherer Sortierkriterien beibehält.

Das macht "Topologisches Sortieren"? Ich dachte immer, das sortiert nur einen Graphen. Welches Sortierverfahren behält 'die Reihenfolge früherer Sortierkriterien' nach erneutem 'Sortieren nach einem anderen Kriterium' bei? Ich kenne Datenstrukturen, die das machen, aber keine Sortierverfahren. Ach, auch egal. Wir wissen ja, was gemeint ist.

[Der_Unwissende]

Hi,
dachte eigentlich topologisches Sortieren besagt nur, dass nicht alle Elemente Paarweise vergleichbar sind. Also nimmt man "zufällig" ein Element und sortiert alle Elemente, die sich mit diesem Vergleichen lassen. Nun schaut man sich die Menge der unbetrachteten Elemente an und geht wieder so vor, zum Schluß erhält man also eine Sortierung, dass für jede Teilmenge von paarweise vergleichbaren Elementen sortiert ist, doch die Reihenfolge dieser Teilmengen wäre dann beliebig.
Aber klar, kenne ich auch am ehesten im Zusammenhang mit Graphen und kann es auch noch falsch in Erinnerung haben (begegnet mir eher selten als Begriff).

Was Merge- und Quicksort angeht, so sollte man wirklich nicht vergessen, dass die Asymptotische Laufzeit konstante Faktoren versteckt (sonst stellt sich schnell die Frage warum Quicksort und nicht Bubblesort, beide O(n^{2})), aber umsonst heißt der Quicksort nicht Quicksort. Amortisiert komme ich ja auch nur auf O(n*log n), aber was wichtiger ist, wie alzmair schon sagte, ich muss immer die ganze Menge im Speicher halten.

Also welche Sortierung die schnellste ist (immerhin auch in linearer Zeit möglich), hängt doch stark von der Menge der Daten und der Art des Speichers ab, sollte hier aber nicht das Problem sein.

[leddl]

Zitat:

Zitat von alzaimar

Übrigens ist laut der grauen Theorie Mergesort im Gegensatz zu Quicksort vom Laufzeitverhalten auch im Worst-Case-Bereich optimal. Davon merkt man beim In-Memory-sortieren zwar Nichts, aber beim externen Sortieren sehr wohl: Dafür wurde Mergesort (Stichwort: Bänder) auch entwickelt.

Deswegen hab ich Mergesort vorgeschlagen. ;) Dessen WorstCase-Verhalten enstpricht dem AverageCase von QuickSort (O(n*logn))

Zitat:

Zitat von alzaimar

Das macht "Topologisches Sortieren"? Ich dachte immer, das sortiert nur einen Graphen. Welches Sortierverfahren behält 'die Reihenfolge früherer Sortierkriterien' nach erneutem 'Sortieren nach einem anderen Kriterium' bei? Ich kenne Datenstrukturen, die das machen, aber keine Sortierverfahren. Ach, auch egal. Wir wissen ja, was gemeint ist.

Keine Ahnung, ob topologisches Sortieren das macht, der Begriff sagt mir nichts :zwinker:
Ich gehe nur davon aus, daß eben das stabile Sortierverfahren gemeint war.
Bei stabilen Sortierverfahren ist sicher, daß bei Übereinstimmen zweier Elemente (nach dem jeweiligen Sortierkriterium) die bisherige Sortierung beibehalten wird. Das ist bei instabilen Verfahren, wie zB QuickSort nicht zwingend der Fall.

Bsp:

Code:

10-a
13-g
17-c
14-c
21-r
11-u
13-h

Wir sortieren erstmal nach den Zahlen:

Code:

10-a
11-u
13-g
13-h
14-c
17-c
21-r

Dann nach den Buchstaben

Code:

10-a
14-c
17-c
13-g // g und h sind bei 13 in der  
13-h // richtigen Reihenfolge
21-r
11-u

Es ist jetzt hier gewährleistet, daß gleiche Zahlen nach dem 2. Sortieren auch immer noch jeweils richtig nach Buchstaben sortiert sind.

PS: Ich hätte vielleicht ein aussagekräftigeres und besseres Beispiel wählen können, aber ich hab keine Lust dazu gehabt :stupid: Hoffe, das is trotzdem halbwegs klar geworden, sonst frag nochmal. ;)

[xaromz]

Hallo,

hier findet sich eine Funktion, die die "Natürliche Sortierung" (so heisst das Ganze) unterstützt. Funktioniert genauso wir CompareString o. ä.

Gruß
xaromz

[alzaimar]

@leddl: Mein Vorschlag basiert auf einer totalen Ordnung und sortiert nur ein Mal, sodass der Unterschied zwischen 'stabilen' und 'instabilen'Sortierverfahren obsolet ist. Oder anders herum: Jedes Sortierverfahren wird bei einer totalen Ordnungsfunktion immer korrekt und 'stabil' sein, weil eben die Elemente immer eine eindeutige Reihenfolge haben.

Deshalb mein Vorschlag, eine totale Ordnung auf die Titelliste über die Vergleichsfunktion abzubilden und dann ein X-beliebiges Sortierverfahren zu verwenden.

[Der_Ventilator]

Zitat:

Zitat von xaromz

Hallo,

hier findet sich eine Funktion, die die "Natürliche Sortierung" (so heisst das Ganze) unterstützt. Funktioniert genauso wir CompareString o. ä.

Gruß
xaromz

Danke, durch deinen Hinweiß auf die "Natürliche Sortierung" habe ich nun hier
http://www.delphipraxis.net/internal...t.php?p=250797
das passende gefunden.
Danke an alle.

[ichbins]

Du könntest ja auch den String in ein Array splitten, wobei der Übergang Zahl-Sonstiges (ausser . und , ) und Sonstiges-Zahl jeweils ein neues Array eröffnet:

Aus 'Bitmap2Icon12345.exe' wird ['Bitmap','2','Icon','12345','.exe']. Das musst du dann nur noch nacheinander sortieren, wobei du, wenn es mit inttostr funktioniert, die Zahlenwerte vergleichst.

[Der_Ventilator]

Was heißt nacheinander sortieren?

Sortiere ich nach der ersten Spalte, dann wird nach der ersten Spalte sortiert.
Wie kann ich denn der 2. Spalte sagen, dass sie nur innerhalb der gleichen der 1. Spalte sortieren soll?

Soll ich die 1. Spalte abgehen und dann nur die Teile, in denen die jeweilige Zeile den nachfolgenden Zeilen gleich ist, einem Sortieralgortihmus unterwerfen?

Oder gibts da einfachere Möglichkeiten?

[Der_Ventilator]

Zitat:

Zitat von Der_Ventilator

Danke, durch deinen Hinweiß auf die "Natürliche Sortierung" habe ich nun hier
http://www.delphipraxis.net/internal...t.php?p=250797
das passende gefunden.
Danke an alle.

OK, wie oben genannt wird dort folgende Funktion angeboten:

Delphi-Quellcode:

//****************************************************************************// 
function NatCompareText(const S1, S2: WideString): Integer; 
begin 
  SetLastError(0); 
  Result := CompareStringW(LOCALE_USER_DEFAULT, 
                           NORM_IGNORECASE or 
                           NORM_IGNORENONSPACE or 
                           NORM_IGNORESYMBOLS, 
                           PWideChar(S1), 
                           Length(S1), 
                           PWideChar(S2), 
                           Length(S2)) - 2; 
  case GetLastError of 
    0: ; 
    ERROR_CALL_NOT_IMPLEMENTED: Result := DumbItDownFor95(S1, 
                                                          S2, 
                                                          NORM_IGNORECASE or 
                                                          NORM_IGNORENONSPACE or 
                                                          NORM_IGNORESYMBOLS); 
  else 
    RaiseLastOSError; 
  end; 
end; 
//****************************************************************************// 
//****************************************************************************//   

//Und falls es doch Probleme gibt (wurde im PSDK extra drauf hingewiesen): 

   
function DumbItDownFor95(const S1, S2: WideString; CmpFlags: Integer): Integer; 
var 
  a1, a2: AnsiString; 
begin 
  a1 := s1; 
  a2 := s2; 
  Result := CompareStringA(LOCALE_USER_DEFAULT, CmpFlags, PChar(a1), Length(a1), 
    PChar(a2), Length(a2)) - 2; 
end;

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

[alzaimar]

Ich verweise nochmal auf meinen Beitrag auf der vorigen Seite, in dem ich genau erklärt habe, wie man das anstellen kann, so dass es garantiert funktioniert. Kein Windows kann wissen, wie deine Titel strukturiert sind, das weisst nur Du. Also musst Du die Titel auseinanderpflücken und getrennt sortieren. So schwer ist das doch nicht. Außer, die Title sind immer wieder anders sortiert, aber dann kann auch der beste Rechner Nichts ausrichten...

Und wenn Du willst, dass '2' kleiner sein soll, also '14', dann versuchs mal mit 'StrToInt' o.ä.

[Phoenix]

Zitat:

Zitat von leddl

as hat im übrigen auch bei großen Datenmengen ne bessere Laufzeit als dein Quicksort. Das hat nämlich im worst Case O(n²), MergeSort nur O(n*logn).

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.

[xaromz]

Hallo,

Zitat:

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:

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:

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:

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:

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:

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:

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:

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.

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:

Zitat von glkgereon

mein Algo kann Ganze Zahlen in linearer Zeit sortieren.

Klappt nicht.

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:

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.

[glkgereon]

Zitat:

Zitat von alzaimar

Zitat:

Zitat von glkgereon

mein Algo kann Ganze Zahlen in linearer Zeit sortieren.

Klappt nicht.

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:

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.

wie ich bereits sagte^^

aber es geht ja ums prinzip :-P

BTW behaupte ich, das man die Einschränkungen bezügklich des Schlüssels aufheben kann...aber nicht vor Sylvester^^

[alzaimar]

Zitat:

Zitat von glkgereon

BTW behaupte ich, das man die Einschränkungen bezügklich des Schlüssels aufheben kann...aber nicht vor Sylvester^^

Hinterher auch nicht. :mrgreen:
Du wirst es nicht schaffen, ein Array mit beliebigem Schlüssel mit einem Aufwand von weniger als O(n log n) zu sortieren. Aber ich lass mich gerne überraschen.

[glkgereon]

Zitat:

Zitat von alzaimar

Zitat:

Zitat von glkgereon

BTW behaupte ich, das man die Einschränkungen bezügklich des Schlüssels aufheben kann...aber nicht vor Sylvester^^

Hinterher auch nicht. :mrgreen:
Du wirst es nicht schaffen, ein Array mit beliebigem Schlüssel mit einem Aufwand von weniger als O(n log n) zu sortieren. Aber ich lass mich gerne überraschen.

Die idee ist einfach...ich werde versuchen, jeden beliebigen schlüsseltypen in einen Integer umzuformen...ob das klappt, keine Ahnung^^