Untere Schranke für Sorter von binären Zahlen

Neue Frage »

Auf diesen Beitrag antworten »
JROppenheimer Untere Schranke für Sorter von binären Zahlen

edit* ich muss mich entschuldigen, ich schreibe mal lieber die aufgabe hier hin, vlt hab ich was falsch verstanden:

0-1 Folgen

In dieser Aufgabe analysieren wir die Komplexität des Sortierproblems bei Eingaben, in welchen nur Zahlen aus der Menge {0,1} vorkommen

a) Begründen sie, warum die untere Schranke von Omega(n log n) für die Laufzeit vergleichsorientierter Sortieralgorithmen, welche nur dieses Problem lösen, nicht gültig ist.

Mein Problem ist jetzt erstmal, es stellt sich mir die frage ob hier 01011, 01100,... gemeint ist oder 0,0,1,1,0,1,0,1,1,1,0,1

Mir fehlt hier absolut der Zugang ...
 
Auf diesen Beitrag antworten »
kiste

gemeint ist letzteres. s. http://de.wikipedia.org/wiki/Bucketsort
Auf diesen Beitrag antworten »
JROppenheimer

Zitat:
bucket „Eimer“) ist ein stabiles Sortierverfahren, das eine Liste in linearer Laufzeit sortieren kann, da es nicht auf Schlüsselvergleichen basiert


Zitat:
Begründen sie, warum die untere Schranke von Omega(n log n) für die Laufzeit vergleichsorientierter Sortieralgorithmen


mit Radixsort hätte ich das auch begründen können, aber die sind ja beide nicht vergleichsbasierend.
Auf diesen Beitrag antworten »
kiste

Ok dann eben anders Augenzwinkern
Führe doch einmal einen Quicksortschritt durch.
 
Auf diesen Beitrag antworten »
JROppenheimer

danke für die hilfe, mitlerweile hab ichs linear gelöst.

alle 1en nach rechts, alle 0en nach links das ght linear und sortiert das ganze großes Grinsen

vielen dank!
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »