Best sort
Re: Best sort
I don't know what lakh numbers are.
War ruins the life and health of untold numbers of innocent children.
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.
War ruins the life and health of untold numbers of innocent children.
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.)
War ruins the life and health of untold numbers of innocent children.
Re: Best sort
That depends on the degree of sorting and the sorting algoritm.
In general you can't say what the minimal time will be,
War ruins the life and health of untold numbers of innocent children.
-
- Posts: 55
- Joined: Thu Mar 29, 2012 12:55 pm
- 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 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.
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
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.
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.