Hallo zusammen,
bei der Lektüre vom Cormen und Wikipedia ist mir etwas aufgefallen, und ich bin mir nicht sicher ob meine Vermutung stimmt:

Es gibt keinen (vergleichenden) Sortieralgorithmus der stabil, in-place und in 0(n*logn) ist.


Wäre über Hinweise dankbar :)
(Ja ich habe Cormen durchgeschaut, Wiki, etc. aber vielleicht bin ich dämlich)

Hehe. Solange ich keinen mathematischen Beweis gesehen habe bleibe ich bei der Aussage "Vielleicht gibt es einen, der ist aber der Menschheit nicht bekannt" [25] Mir geht es ähnlich: Ich kenne keinen, der alles drei ist.

Tim Sort und Merge Sort würden mir jetzt so spontan einfallen

Merge sort is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, meaning that the implementation preserves the input order of equal elements in the sorted output. It is a divide and conquer algorithm. Merge sort was invented by John von Neumann in 1945.[1]

http://en.wikipedia.org/wiki/Merge_sort

Die sind aber beide nicht in-place, oder?

Die sind beide out-of place :)

Das ist schon interessant - Das man bis jetzt noch keinen Sortieralg. kennt der das "beste" aus allen Welten vereinigt. Finde aber auch keinen Beweis das so es so einen nicht geben kann.

Außer das hat hängt vielleicht irgendwie mit den Beweis zusammen, dass vergleichende Sortierverfahren bestenfalls in n+logn liegen.
Begründet wird das im Cormen mit einem Entscheidungsbaum der Höhe h, dessen Blätter diese Vergleichsentscheidungen sind. Möglicherweise ist die Menge dieser Entscheidungen in-place einfach nicht realisierbar, außer man verwendet sehr spezielle Strukturen wie Heaps.

Man kann doch jeden Sortieralgorithmus mit [latex]\Theta(n log n)[/latex] Platz stabilisieren, indem man alle Elemente unterscheidbar macht:
a,b,c,a,d,b,b,f wird einfach zu (a,0),(b,1),(c,2),(a,3),(d,4),(b,5),(b,6),(f,7) umgeschrieben. (a0,b0) > (a1,b1) gdw. a0>a1 oder a0=a1 und b0>b1.
Aber ich vermute mal, dass so ein Trick nicht gilt und in der Praxis auch kaum relevant sein dürfte :-)

Ich glaube wenn ich diesen "Trick" mit der Unterscheidung richtig verstehe, ist er speichertechnisch betrachtet abhänig von n und würde durch den zusätzlichen Schlüssel dann abhänig von n "mehr speicher" benötigen als für die ursprüngliche Eingabe.


Allen aber an der Stelle vielen Dank! Ich merke hier im Forum immer wieder wie spannend Informatik doch ist.

Wie gesagt, man benötigt [latex]\Theta(n\log{n})[/latex] mehr Platz.

zu Merge Sort

Das Verfahren arbeitet bei Arrays in der Regel nicht in-place, es sind dafür aber (trickreiche) Implementierungen bekannt. Verkettete Listen sind besonders geeignet zur Implementierung von Mergesort, dabei ergibt sich die in-place-Sortierung fast von selbst.

aus http://de.wikipedia.org/wiki/Mergesort

Timsort: Worst case space complexity O(n)

http://en.wikipedia.org/wiki/Timsort

Das ist für mich in-Place.

O(n) heißt linearer Speicher, nicht in-place.

Timsort braucht nach http://en.wikipedia.org/wiki/Sorting_algorithm O(n) zusätzlichen Speicher.

O(n) heißt linearer Speicher, nicht in-place.

Timsort braucht nach http://en.wikipedia.org/wiki/Sorting_algorithm O(n) zusätzlichen Speicher.

arg mist, da war ja was -.-


http://www.springerlink.com/content/bx6d9xv8p6w3d3p4/

deutet darauf hin das es sowas gibt:

[attachment=514]