@Ilya: As I said in my earlier post,
https://groups.google.com/d/msg/algogeeks/QyNBGrMHaCs/evd8iLvP2CUJ, use a
radix sort. It is O(n) in time, and has an O(n) space requirement.
Dave
On Sunday, April 22, 2012 6:55:03 PM UTC-5, Ilya Albrekht wrote:
> I'm not aware of any O(n) sort algorithms. Any (known) sort algorithm can
> have O(n) iff array is already sorted - kinda trivial case.
>
> So sort will not work for this task...
>
> On Wednesday, 18 April 2012 06:41:38 UTC-7, Dave wrote:
>>
>> @Viharri: A solution seems to require an O(n) sorting algorithm, and
>> since sorting by comparison is O(n log n), the algorithm must use one of
>> the other types of O(n) sorting algorithms. Since the data are not integers
>> in a bounded range, I suggest using a radix sort, carrying along an array
>> of indices. I.e., form an array of indices {0, 1, 2, ..., n-1} and perform
>> the same data movements on it as on the original data. When the original
>> data are sorted, then the array of indices will be the desired result.
>>
>> Dave
>>
>> On Wednesday, April 18, 2012 8:07:33 AM UTC-5, VIHARRI wrote:
>>
>>> Can anybody give an O(n) algorithm for the following problem.
>>>
>>> Suppose if we have an array, I would like to construct an array with the
>>> elements which specify their corresponding position in the sorted array.
>>>
>>> For example if the array is { 0.87, 0.04, 0.95, 0.12, 0.36 } then the
>>> sorted array would be { 0.04, 0.12, 0.36, 0.87, 0.95 }.
>>> Then output array would be {3, 0, 4, 1, 2 }.
>>>
>>> Hope I'm clear...
>>>
>>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/i4ttCNNP1LMJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
