+- FB18.de - Das Informatikforum ( /mybb )
+-- Forum: Bachelorstudieng ( /forumdisplay.php?fid=112 )
+--- Forum: PM Praktische Informatik ( /forumdisplay.php?fid=98 )
+--- Thema: Sortieralgorithmen ( /showthread.php?tid=12015 )
Sortieralgorithmen - Anonymer User - 16.03.2011 00:18
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)
RE: Sortieralgorithmen - Vollkorn - 16.03.2011 00:41
Hehe. Solange ich keinen mathematischen Beweis gesehen habe bleibe ich bei der Aussage "Vielleicht gibt es einen, der ist aber der Menschheit nicht bekannt"
Mir geht es ähnlich: Ich kenne keinen, der alles drei ist.
RE: Sortieralgorithmen - Raid - 16.03.2011 01:44
Tim Sort und Merge Sort würden mir jetzt so spontan einfallen
Zitat:
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.
http://en.wikipedia.org/wiki/Merge_sort
RE: Sortieralgorithmen - UncleOwen - 16.03.2011 07:36
Die sind aber beide nicht in-place, oder?
RE: Sortieralgorithmen - Anonymer User - 16.03.2011 08:51
Die sind beide out-of place :)
RE: Sortieralgorithmen - Anonymer User - 16.03.2011 08:57
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.
RE: Sortieralgorithmen - Wulf - 16.03.2011 10:06
Man kann doch jeden Sortieralgorithmus mit
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 :-)
RE: Sortieralgorithmen - Anonymer User - 16.03.2011 12:00
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.
RE: Sortieralgorithmen - Wulf - 16.03.2011 13:45
Wie gesagt, man benötigt
RE: Sortieralgorithmen - Anonymer User - 16.03.2011 14:27
zu Merge Sort
Zitat:
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
RE: Sortieralgorithmen - Raid - 17.03.2011 21:04
Timsort: Worst case space complexity O(n)
http://en.wikipedia.org/wiki/Timsort
Das ist für mich in-Place.
RE: Sortieralgorithmen - Anonymer User - 18.03.2011 01:37
O(n) heißt linearer Speicher, nicht in-place.
Timsort braucht nach http://en.wikipedia.org/wiki/Sorting_algorithm O(n) zusätzlichen Speicher.
RE: Sortieralgorithmen - Raid - 19.03.2011 01:30
Anonymer User schrieb:
O(n) heißt linearer Speicher, nicht in-place.
Timsort braucht nach http://en.wikipedia.org/wiki/Sorting_algorithm O(n) zusätzlichen Speicher.
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]