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