The divide and conquer algorithm for finding the median is described in http://en.wikipedia.org/wiki/Selection_algorithm.
Dave On Apr 22, 6:02 am, "Varun S V" <[EMAIL PROTECTED]> wrote: > Hi, > > Im a bit confused as how DAndC happens in O(n) time. Doesn't it take > O(nlogn) time by the way the algo has been described above? > we have to divide the array every time and again work on both the sub > arrays. Can you kindly explain how does this take O(n) time? > > 2008/4/22 Pramod Negi <[EMAIL PROTECTED]>: > > > > > make a partition about media as a pivot element > > > On 4/22/08, 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 -~----------~----~----~----~------~----~------~--~---
