[OT] stable algorithm with complexity O(n)

[Duncan Booth]

"Diez B. Roggisch" <deets at nospam.web.de> wrote:

> David Hláčik schrieb:
>> 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!
> 
> Unless I grossly miss out on something in computer science 101, the 
> lower bound for sorting is O(n * log_2 n). Which makes your task 
> impossible, unless there is something to be assumed about the 
> distribution of numbers in your sequence.
> 
> Who has given you that assignment - a professor? Or some friend who's 
> playing tricks on you?
> 
I think you must have fallen asleep during CS101. The lower bound for 
sorting where you make a two way branch at each step is O(n * log_2 n), but 
if you can choose between k possible orderings in a single comparison you 
can get O(n * log_k n).

To beat n * log_2 n just use a bucket sort: for numbers with a known 
maximum you can sort them digit by digit for O(n log_k n), and if you don't 
restrict yourself to decimal then k can be as large as you want, so for the 
problem in question I think you can set k=n and (log_n n)==1 so you get 
O(n)

i.e. digit by digit bucket sort the numbers in base n.

Something like (untested):

n = len(data)
buckets1 = [[] for i in range(n)]
buckets2 = [[] for i in range(n)]

for x in data:
   buckets1[x % n].append(x)

for x in (v for b in buckets1 for v in reversed(b)):
   buckets2[x // n].append(x)

for x in (v for b in buckets2 for v in b):
   print x

All loops are order n (the last two have about 2*n steps).

I lied about the untested:

>>> def f(data):
	n = len(data)
        buckets1 = [[] for i in range(n)]
        buckets2 = [[] for i in range(n)]

        for x in data:
           buckets1[x % n].append(x)

        for x in (v for b in buckets1 for v in reversed(b)):
           buckets2[x // n].append(x)

        for x in (v for b in buckets2 for v in b):
           print x

>>> import random
>>> data = [ random.randint(1,100) for i in range(10)]
>>> f(data)
1
16
30
35
70
70
75
76
82
99