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

[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 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 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
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 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 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 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 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.