Sortieren mit max. O(n) ?

[Worn]

Hallo,

ich hab mal wieder eine Aufgabe zu lösen wo ich nicht so recht weiß wie ich die angehen soll.

Es gibt ein nicht sortiertes Zahlenarray b der Länge n. Dieses Array enthält nur werte zwischen 1 und 100n. (also bei n= 5 hat es 5 Zahlen zwischen 1 und 500)

Jetzt soll man einen Algorithmus skizzieren, der dadurch, dass es einen eingeschränkten Wertebereich gibt (100n) nur eine Komplexität von O(n) aufweist.

Tja da ich in Algorithmik jetzt kein Licht bin frag ich hier mal nach, hat einer eine Idee?

Danke

Grüße

Ben

[Klotzkopp]

Stichwort: Bucketsort.

[Crush]

Oder Radixsort

[derJan]

Allgemeine und spezielle Sortieralgorithmen + Suchalgorithmen

da gibts n ganzen Haufen, such dir was raus...