@Nagendra : As earlier told Refer Pg 189, Cormen, an algorithm is given to find the Kth largest element in O(n) *worst* time complexity.
@Dufus: yeah, am pretty sure that the algorithm I have described results in K closest elements to median. For e.g. Let the array be 2 5 7 10 11 14 19 45 121 i.e. n= 9 elements and 5 closest medians are required. First determine the median in O(n) time using Linear general selection algorithm - "Median of Medians algorithm"<http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22>by looking for 5th largest element in the array. Median = 11. int compare (int a, int b, int median){ return ( abs(median - a) - abs(median - b)) ; } Rest of the task is similar to first finding the (k)th smallest element in the array |2-11|, |5-11|, |7-11|, |10-11|, |11-11|, |14-11|, |19-11|, | 45-11|, |121-11| i.e. 9, 6, 4, 1, 0, 3, 8, 34, 110 and then partitioning the array around the pivot and returning the first k elements as the solution. Storing the above array in O(n) space and then performing the task would have ease the task but if space is a constraint (constant space), compare function described above can be used. Working for constant space, Using the compare function, let ** the first recursive call SELECT(arr, 0, 8, 5) *for e.g* does partitioning for index 2. The partitioned array for pivot arr[2] = 7 is (10, 11, 14) 7 (2, 5, 19, 45, 121) (order of elements in the bracket may vary depending upon coding). equivalent to (1, 0, 3,) 4 ( 9, 6, 8, 34, 110) for O(n) space case. so 7 is the 4th smallest element. the above calls SELECT (arr, 4, 8, 5 - 4) which *ultimately* partitions the array into (10 , 11, 14, 7,) 5 (2, 19, 45, 121) equivalent to (1, 0, 3, 4,) 6 ( 9, 8, 34, 110) for O(n) space case. the first 5 elements is the required answer. Overall worst case time complexity : O(n), space complexity : O(1). O(n) space simplifies the coding and understanding of the problem. On Tue, Sep 1, 2009 at 6:04 PM, ankur aggarwal <ankur.mast....@gmail.com>wrote: > @shishir > > i could understand > cann u give an example.. > > > > > -- Shishir Mittal Ph: +91 9936 180 121 --~--~---------~--~----~------------~-------~--~----~ 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 algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
