 Pseudocode in 0(n) |
330677
unregistriert
 |
|
Meine Frage:
Ich soll einen Algorithmus in Pseudocode schreiben, welcher ein Feld A mit Wertebereich {1,..(n^2) - 1} in O(n) sortiert
Meine Ideen:
Habe leider keine Ahnung wie ich an die Sache rangehen soll.
|
|
12.11.2014 16:56 |
|
|
|
|
Ist das der originale Wortlaut der Aufgabe?
Es ist nicht möglich, n^2-1 Werte in O(n) zu sortieren, mit dem Mergesort erreichst du O((n^2-1) * log(n^2-1)).
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
12.11.2014 18:32 |
|
|
heikob2
Grünschnabel
Dabei seit: 19.11.2014
Beiträge: 2
|
|
Es ist möglich, da der Wertebereich 1 bis (2^n) - 1 beträgt. Der Algorithmus heißt Bucket-Sort:
- Du legst ein Array "L" von 1 bis( 2^n)-1 an und initialisierst jedes Feld mit null.
- Dann iterierst du durch A und inkrementierst L[A[i]].
- Für die Ergebnismenge iterierst du durch L und fügst falls L[i] > 0, das Element "i" L[i]-mal in diese ein.
=> O(n).
gruß Heiko
|
|
|
19.11.2014 13:03 |
|
|
|
