@illya read the posts in the thread.Count sort is O(n) sorting algorithm.The constraints in this algorithm is that the maximum value of the array to be sorted should not be large. Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com
On Mon, Apr 23, 2012 at 5:25 AM, Ilya Albrekht <[email protected]>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/-/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. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. 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.
