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 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.