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/-/FJloKhIFv_EJ.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
