[algogeeks] Re: Sorting o(n) time
Hi all, Quoted from Wikipedia: Pigeonhole sorting, also known as count sort, is a sorting algorithm that takes linear time (Θ(n)), which is the best possible performance for a sorting algorithm since one must inevitably look at each of the elements being sorted at least once, regardless of the sorting algorithm. However, pigeonhole sorting is only practical if the objects you are sorting fall within (or can be mapped into) a range of possible values that is small compared to the size of the list to be sorted. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Sorting o(n) time
Yeah, after finding the k-th element there is no need for further partitioning. This is logically true indeed. But in this case, I guess you have to do it for determining who'll get the Samosas and who the Gulabjamuns !!. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Sorting o(n) time
Do we have to partition after finding the kth element ? Will the Array not be partitioned when the base condition is met ? Amal. On 3/16/07, Rajiv Mathews [EMAIL PROTECTED] wrote: On 3/16/07, Karthik Singaram L [EMAIL PROTECTED] wrote: How would the median algorithm get the top k elements? I think what he meant was, use the median by parting-in-5 algorithm to find the kth largest element. This can be done in O(n). Then just partition around this element to get the top k elements, O(n). -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Sorting o(n) time
On 3/16/07, Karthik Singaram L [EMAIL PROTECTED] wrote: How would the median algorithm get the top k elements? I think what he meant was, use the median by parting-in-5 algorithm to find the kth largest element. This can be done in O(n). Then just partition around this element to get the top k elements, O(n). -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Sorting o(n) time
You could try the quick-sort algo with these further modifications : every time you partition the list (assuming ascending) you leave out the entire working for the right hand part iff the size of the left hand part is = m (m is the top m elements that you need). NB : Here left hand part indicates the part to the left of the pivot i.e. right from the beginning of the array. This on an average case should be able to accomplish the task in O(n) time. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Sorting o(n) time
you can sort the students list according to marks in o(n) time by using RADIX SORT. On 3/14/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: Dean of Computer Science department wants to keep the motivation levels of students of data structure course high by giving incentives. He has suggested that after the second minor the top lon students be distributed samosas and the next sqrt(n) students be given gulab jamuns. However, he has stipulated that we cannot sort the student roll list according to marks (which would také time) but should use data structures skills to determine who gets what in O(n) time??? -- *** 30 years from now it doesn't matter which shoe you wore,which branded jean you wore..what all matters is WHAT YOU HAVE LEARNED AND HOW YOU HAVE USED IT. http://students.iiit.ac.in/~koushik_c --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
