@Bashrc: An additional constraint is that the data be integers. Counting sort isn't applicable to floats, doubles, or character strings. That's why I suggested using a radix sort. It is actually like a counting sort on successive bit fields of the data. Dave
On Sunday, April 22, 2012 8:37:26 PM UTC-5, .bashrc wrote: > @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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/_g7VGXor1vQJ. 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.
