Page 1 of 1

Best sort

Posted: Sun Dec 24, 2017 9:19 am
by S_r
Let there be a million numbers from one to million randomly placed in array, what is the minimum running time you can sort it in? I will reply at end. I really want everyone to give their answers

Re: Best sort

Posted: Sun Dec 24, 2017 9:31 am
by hk
I don't know what lakh numbers are.

Re: Best sort

Posted: Sun Dec 24, 2017 9:34 am
by S_r
Ten lakhs = a million. Sorry, I didn't know lakhs wasn't known to you

Re: Best sort

Posted: Sun Dec 24, 2017 11:40 am
by hk
I don't think many members of Project Euler would have known what a lakhs is.
Be careful not to use purely local concepts.

Re: Best sort

Posted: Sun Dec 24, 2017 1:25 pm
by v6ph1
I think it's possible for PE users to search unknown words - and there are many interesting number words. - Except the western concepts of thousand, million,...

@Topic:
Sorting is O(n*log n)
The factor depends on the architecture: lets assume 5.
1000000*20*5 = 100000000 = 10^8 Ops
Using a 4GHz CPU, we have 25ms.

Re: Best sort

Posted: Sun Dec 24, 2017 2:20 pm
by hk
v6ph1 wrote:
Sun Dec 24, 2017 1:25 pm
I think it's possible for PE users to search unknown words - and there are many interesting number words. - Except the western concepts of thousand, million,...
Yes that is possible of course.
However, I think it would be better to avoid such situations. (Unless you are on a linguistics site of course.
Or if those interesting number words are the subject of your post. At least you should be aware you are using words not common to your readers.)

Re: Best sort

Posted: Sun Dec 24, 2017 3:21 pm
by hk
v6ph1 wrote:
Sun Dec 24, 2017 1:25 pm

@Topic:
Sorting is O(n*log n)
That depends on the degree of sorting and the sorting algoritm.
In general you can't say what the minimal time will be,

Re: Best sort

Posted: Sun Dec 24, 2017 3:38 pm
by Svartskägg
S_r wrote:
Sun Dec 24, 2017 9:19 am
a million numbers from one to million
This can be interpreted as a million random numbers from the range 1 to 1000000 or as precisely all the numbers in the range.

Re: Best sort

Posted: Mon Dec 25, 2017 12:13 am
by v6ph1
Unless a predictable randomness, O(n*log n) is the necessary time for sorting.
O(n) can only be achieved if the sequence has a defined order.

It doesn't matter if there are all the numbers in randomized order (I would assume from the description) or 1 million random numbers (up to 1million).

So my answer is 25ms (depending on the processing unit).

Re: Best sort

Posted: Mon Dec 25, 2017 7:16 am
by traxex
v6ph1 wrote:
Mon Dec 25, 2017 12:13 am
Unless a predictable randomness, O(n*log n) is the necessary time for sorting.
O(n) can only be achieved if the sequence has a defined order.
That is only true for comparison-based sorting algorithms. Both counting sort and radix sort could be used here since the range of values is known.

Whether O(n) is faster than O(n log n) in practice is another question. Million is a small number.

Re: Best sort

Posted: Mon Dec 25, 2017 3:07 pm
by S_r
We can take an array of size n+1 and simply assign a[n]=n and it will be sorted no comparison needed. Even if it is not from 1 to n and is within a range we can use a[n+minimum number]=n. Sorry for my english

Re: Best sort

Posted: Mon Dec 25, 2017 3:16 pm
by S_r
Tell me if it is something remarkable

Re: Best sort

Posted: Mon Dec 25, 2017 3:43 pm
by traxex
The question is not completely silly. Sometimes sorting needs to be done in-place, because the array actually contains pairs (n,x) where the n is used for sorting and x is some data attached to it. Creating a new array that just contains the n values would not be useful, because what we really want is to have the x values sorted with respect to the n values.

Sorting a random permutation in-place can be done in O(n) time, resolving one cycle at a time.