Best sort

General chat, humour, riddles, logic/lateral/word puzzles...
Post Reply
User avatar
S_r
Posts: 32
Joined: Thu Aug 10, 2017 5:37 am

Best sort

Post 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
Last edited by S_r on Sun Dec 24, 2017 11:53 am, edited 2 times in total.
User avatar
hk
Administrator
Posts: 12164
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Best sort

Post by hk »

I don't know what lakh numbers are.
Image
War ruins the life and health of untold numbers of innocent children.
User avatar
S_r
Posts: 32
Joined: Thu Aug 10, 2017 5:37 am

Re: Best sort

Post by S_r »

Ten lakhs = a million. Sorry, I didn't know lakhs wasn't known to you
User avatar
hk
Administrator
Posts: 12164
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Best sort

Post 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.
Image
War ruins the life and health of untold numbers of innocent children.
v6ph1
Posts: 134
Joined: Mon Aug 25, 2014 7:14 pm

Re: Best sort

Post 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.
Image
User avatar
hk
Administrator
Posts: 12164
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Best sort

Post 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.)
Image
War ruins the life and health of untold numbers of innocent children.
User avatar
hk
Administrator
Posts: 12164
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Best sort

Post 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,
Image
War ruins the life and health of untold numbers of innocent children.
Svartskägg
Posts: 55
Joined: Thu Mar 29, 2012 12:55 pm
Location: Sweden

Re: Best sort

Post 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.
Image
320641_5486fc18ea1dcc4e9a8f29c7677a5c19 <-- my friend key
v6ph1
Posts: 134
Joined: Mon Aug 25, 2014 7:14 pm

Re: Best sort

Post 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).
Image
traxex
Posts: 66
Joined: Thu Oct 19, 2017 1:30 pm

Re: Best sort

Post 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.
Technically, everyone is full of himself.
User avatar
S_r
Posts: 32
Joined: Thu Aug 10, 2017 5:37 am

Re: Best sort

Post 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
User avatar
S_r
Posts: 32
Joined: Thu Aug 10, 2017 5:37 am

Re: Best sort

Post by S_r »

Tell me if it is something remarkable
traxex
Posts: 66
Joined: Thu Oct 19, 2017 1:30 pm

Re: Best sort

Post 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.
Technically, everyone is full of himself.
Post Reply