[OT] stable algorithm with complexity O(n)
Arnaud Delobelle
arnodel at googlemail.com
Sat Dec 13 17:18:34 EST 2008
"David Hláčik" <david at hlacik.eu> writes:
> Hi guys,
>
> i am really sorry for making offtopic, hope you will not kill me, but
> this is for me life important problem which needs to be solved within
> next 12 hours..
>
> I have to create stable algorithm for sorting n numbers from interval
> [1,n^2] with time complexity O(n) .
>
> Can someone please give me a hint. Would be very very thankful!
>
> Thanks in advance!
> D.
I don't have an algorithm but I have an implementation :)
def sort2(numbers):
"sort n positive integers in O(n) provided that they are all < n^2"
N = len(numbers)
units = [[] for i in xrange(N)]
tens = [[] for i in xrange(N)]
for n in numbers:
units[n % N].append(n)
for l in units:
for n in l:
tens[n / N].append(n)
return [n for l in tens for n in l]
--
Arnaud
More information about the Python-list
mailing list