The divide and conquer algorithm for finding the median is described in http://en.wikipedia.org/wiki/Selection_algorithm.
Dave On Apr 22, 4:43 am, "Varun S V" <[EMAIL PROTECTED]> wrote: > Hi Dave, > > Can you kindly eloborate your algorithm? > How can we modify a single array in O(n) time, such that the median comes to > become the n/2th element and smaller elements comes to the left side and > larger elements comes to the right side? Kindly explain in detail. > > 2008/4/22 Pramod Negi <[EMAIL PROTECTED]>: > > > > > i didnt get what u want to so say (the bold lines) > > > On 4/21/08, Dave <[EMAIL PROTECTED]> wrote: > > > > Use a divide-and-conquer algorithm to find the median, rearranging the > > > array so that the values less than the median precede it in the array > > > and the values greater than the median follow it. So the median is a(n/ > > > 2).* Now use the divide-and-conquer algorithm twice more to locate the > > > (n/2-k)th and (n/2+k)th elements*. Finally, march out both directions > > > from n/2, selecting the closest elements to a(n/2). Each of these > > > operations can be done in O(n), so the total algorithm is O(n). > > > > Dave > > > > On Apr 21, 9:35 am, Algo <[EMAIL PROTECTED]> wrote: > > > > hi this is prob 9-3.7 of CLRS , anybody having a clue??? > > > > > Describe an O(n)-time algorithm that, given a set S of n distinct > > > > numbers and a positive > > > > integer k ≤ n, determines the k numbers in S that are closest to the > > > > median of S > > > > > thanks in advance..- Hide quoted text - > > - Show quoted text - --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
