[CentOS] [OT] stable algorithm with complexity O(n)

Sun Dec 14 00:22:59 UTC 2008
Marko Vojinovic <vvmarko at panet.co.yu>

> >> 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!
> >
> > Merge sort? Insertion sort? Selection sort? timsort?
> 
> Well, something with linear complexity O(n) which i have to prove,
>
> Merge sort, Insertion sort or selection sort does not have O(n) complexity.
>
> I believe that something like RadixSort, CountingSort, BucketSort
> altought i am not sure

Radix is O(n ln n), so no-go for you. I'm not familiar with other names. 
However, what you need is what is called the "generation counter" algorithm 
(afaik its name).

Basically, count the number of appearances of every number in your set. If you 
have a set a priori bounded from above and below --- which you do,
[1, n^2] --- you first allocate an array of integers of length n^2. Set all 
elements to zero, go through your set that is to be sorted, and whenever you 
find a number k go and increment the k-th element of your generation array. 
You need one for-loop to go through your set, and after that another for loop 
to print the output from the generation set --- go through the whole set from 
1 to n^2, and if the value of k-th element is nonzero, print number k 
appropriate number of times.

For example, if you have the set {1,8,5,3,5,9,6,2,2,4,3,5} and you are told 
that items are always in the interval [1,10], you form a generation set:

 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |       <- labels
 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |   0 |       <- initial values 

and you fill it by counting the number of appearances for every element of 
your set (first for-loop):

 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |       <- labels
 | 1 | 2 | 2 | 1 | 3 | 1 | 0 | 1 | 1 |   0 |       <- final values 

Then you go through it and type each "label", "field value" number of times 
(second for-loop):

{1,2,2,3,3,4,5,5,5,6,8,9}.

The algorithm is basically consisted of two consequent for-loops, which should 
make its complexity O(n), afaik. However, I'll leave the proof to you. ;-)

Btw, it is a well known fact that given a set of n elements and no other 
information, the best algorithm for sorting is going to be at least O(n ln n) 
or worse. However, if you are given some other information about your set 
(like the extrema of its image or some such info), you can in improve the 
sorting speed, O(n) being the linear, best-case scenario. Generation counter 
algorithm is a textbook example of this.

Or you can wait for quantum computers to be invented. They have more
powerful algorithms, due to the use of qubits instead of bits... ;-)

HTH, :-)
Marko