Best sort
Re: Best sort
I don't know what lakh numbers are.
Re: Best sort
Ten lakhs = a million. Sorry, I didn't know lakhs wasn't known to you
Re: Best sort
I don't think many members of Project Euler would have known what a lakhs is.
Be careful not to use purely local concepts.
Be careful not to use purely local concepts.
Re: Best sort
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.
@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
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.)

 Posts: 55
 Joined: Thu Mar 29, 2012 11:55 am
 Location: Sweden
Re: Best sort
This can be interpreted as a million random numbers from the range 1 to 1000000 or as precisely all the numbers in the range.
320641_5486fc18ea1dcc4e9a8f29c7677a5c19 < my friend key
Re: Best sort
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).
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
That is only true for comparisonbased 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.
Re: Best sort
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
Tell me if it is something remarkable
Re: Best sort
The question is not completely silly. Sometimes sorting needs to be done inplace, 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 inplace can be done in O(n) time, resolving one cycle at a time.
Sorting a random permutation inplace can be done in O(n) time, resolving one cycle at a time.
Technically, everyone is full of himself.