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

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