Re: [OT] stable algorithm with complexity O(n)

Duncan Booth schrieb:
"Diez B. Roggisch" <deets@xxxxxxxxxxxxx> 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)

Thanks. I *totally* forgot about that.

Diez
.

Relevant Pages

  • Re: Sorting by complex alphanumeric data
    ... Access uses 30 as the lower bound for rwo digit ... I didn't know that you could write statements into the sorting and grouping ... most likely could use in the Report Sorting & Grouping what I gave you above ...
    (microsoft.public.access.reports)
  • Re: [OT] stable algorithm with complexity O(n)
    ... I have to create stable algorithm for sorting n numbers from interval ... lower bound for sorting is O. ... To beat n * log_2 n just use a bucket sort: ... maximum you can sort them digit by digit for O, ...
    (comp.lang.python)
  • Re: [OT] stable algorithm with complexity O(n)
    ... I have to create stable algorithm for sorting n numbers from interval ... To beat n * log_2 n just use a bucket sort: ... maximum you can sort them digit by digit for O, ...
    (comp.lang.python)
  • Re: Sorting algorithm when comparison is heavy
    ... asking about sorting things with very expensive compare operations. ... single digit of the long value. ... sorted pile after handling the most significant digit. ...
    (comp.programming)
  • Re: On the complexity of determining whether n numbers are distinct
    ... this can be shown by reducing the problem to one of sorting but the ... bounds for algebraic computation trees" by Michael Ben-Or proves the n ... log n lower bound in the algebraic decision tree model of computation. ...
    (comp.theory)