@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/-/evd8iLvP2CUJ.
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.
