Adaptiertes 2-Phasen-2-Band-Mischen?

[Aqualon]

H!

Ich habe eine Frage zu einem Sortieralgorithmus, der bei Wikipedia erwähnt wird:

http://de.wikipedia.org/wiki/Adaptiertes_2-Phasen-2-Band-Mischen

Hat der wirklich nur Aufwand O(log n)? Und falls ja, warum findet man dazu nichts ausser dem Wikipedia-Artikel? Hat da jemand genauere Infos dazu?

Aqua

[Legolas]

Also für vergleichsbasierte Sortieralgorithmen gilt als untere Grenze O(n logn). Ich denke, daß auch der bei Wikipedia beschriebene Algorithmus vergleichsbasiert ist. Insofern ist das wohl ein Tippfehler.

[Shink]

Stimmt genau. Gäbe es einen General Purpose O(log n) - Sortieralgorithmus, so ginge in der Mathematik einiges schief. Ausserdem:
"Man initialisiert die Liste, indem man für jedes Element die Rückwärtszeiger wie die Vorwärtszeiger auf das nächste Element zeigen lässt." - das alleine dauert schon mal O(n) und mit dem Algorithmus haben wir noch gar nicht angefangen.

Es gibt Algorithmen wie Quicksort, die im Schnitt O(n) brauchen, das ändert aber nichts an ihrer Komplexität von O(n log n).
Nur zur Überlegung: Wie soll man n beliebige Zahlen komplett sortieren, wenn man gar nicht jede behandelt hat und somit gar nicht jeden Wert kennt?

[DocEW]

Also besser als lineare Laufzeit wird's wohl tatsächlich nicht geben...
BTW, Bucketsort ist das schnellste, was mir so einfällt. Hat allerdings eine Randbedingung und ist daher nicht für alles geeignet:
http://de.wikipedia.org/wiki/Bucketsort

[Shink]

Hm, hab grad bemerkt dass Quicksort sogar O(n^2) Worst Case hat.
Zu den Algorithmen mit O(n) wie Bucketsort: Davon hab ich eigentlich noch gar nicht gehört. Seh ich das richtig, dass man die vom Konzept her mit Hashing vergleichen kann? Ansonsten seh ich nicht ein, wie das gehn soll.

[Aqualon]

Bucketsort ist Einsortieren in eine Hashtabelle. Dabei vergleichst du ja nicht und hast deswegen nur Aufwand O(n). Der ist aber nur anwendbar, wenn man weiß, dass die zu sortierenden Elemente zwischen bestimmten Grenzwerten liegen und eine Hashfunktion aufgestellt werden kann.

Für beliebige Zahlen (und seien es nur int-Werte) würde der einfach zuviel Speicher benötigen.

Ich schätze bei dem oben genannten Misch-Verfahren ist der Aufwand O(n*log(n)). Mich hätten nur nähere Infos zu dem Verfahren interessiert, da ich aus der kurzen Beschreibung bei Wikipedia nicht wirklich schlau wäre.

Aqua

Edit: Bucketsort benötigt natürlich eine endliche Menge an zu sortierenden Elementen. Eine Liste von Namen zu sortieren ist damit nicht möglich (da nicht endlich bzw. selbst bei nur 5 Buchstaben bereits 26^5 = ~12Mio mögliche Elemente, von Sonderzeichen ganz zu schweigen), aber es wäre möglich die Namen nach den Anfangsbuchstaben sortiert in Hashtabellen einzuordnen.

[Shink]

Stimmt, danach den Algorithmus zu implementieren ist nicht grad einfach...

[Xmas]

Edit: Bucketsort benötigt natürlich eine endliche Menge an zu sortierenden Elementen. Eine Liste von Namen zu sortieren ist damit nicht möglich (da nicht endlich bzw. selbst bei nur 5 Buchstaben bereits 26^5 = ~12Mio mögliche Elemente, von Sonderzeichen ganz zu schweigen), aber es wäre möglich die Namen nach den Anfangsbuchstaben sortiert in Hashtabellen einzuordnen.
Schau dir mal Radix Sort an, das auf Bucket Sort aufbaut. Ist O(n), und hat dieses Problem nicht.

[Trap]

Radix sort und Bucket sort sortieren nicht durch Vergleichen. Das ist die größte Einschränkung der Verfahren.

[Xmas]

Radix sort und Bucket sort sortieren nicht durch Vergleichen. Das ist die größte Einschränkung der Verfahren.
Das ist nur insofern eine Einschränkung, als dass du bei nicht-"bytegemäßer" Sortierung (lexikalische Sortinerung von Strings beispielsweise) erst einen Algorithmus finden musst, der den Elementen eine eindeutige Integer-Zahl in Sortierreihenfolge zuweist.

Radix Sort kann man übrigens auch für Float-Zahlen modifizieren.

[Trap]

Man muss einen O( n) Algorithmus finden um die Zahlen zuzuweisen, sonst bringt einem Radix/Bucket sort nix. Außerdem sollten die zugewiesenen Zahlen nicht allzu groß sein (2^847389 als Bignum...)
Ich bin mir nicht sicher, dass man das bei Daten ohne vollständige Ordnung machen kann.

Für sehr viele praktische Probleme ist es kein Problem.

[GloomY]

Ich halte von dem Artikel generell nicht viel. Man findet neben dem O(logn) statt O(nlogn) Fehler auch noch andere Ungereimtheiten in diesem recht knappen Text:Einfügen und Löschen ist sehr einfach. Daher ist eine Liste einem Array sehr überlegen.Das ist Bullshit. Eine (doppelt) verkettete Liste ist nicht generell einem Array überlegen. Suchen des m-ten Eintrags geht z.B. ewig langsam in einer verketteten Liste, während man das bei einem Array das sehr schnell über den Index bestimmen kann.

Ansonsten würde man ja nur noch verkettete Listen und Arrays gar nicht mehr benutzen...

Zum Algorithmus: Ich verstehe nicht genau, wie dieser funktionieren soll, aber er erinnert mich recht stark an Merge-Sort.