---

Geschrieben von 330677 am 12.11.2014 um 16:56:

  Pseudocode in 0(n)

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.

---

Geschrieben von eulerscheZahl am 12.11.2014 um 18:32:

 

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)).

---

Geschrieben von heikob2 am 19.11.2014 um 13:03:

  RE: Pseudocode in 0(n)

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