We can use min heap. 1) Build a Min Heap MH of the first m elements (arr[0] to arr[m-1]) of the given array. O(m) 2) For each element, after the mth element (arr[m] to arr[n-1]), compare it with root of MH. a) If the element is greater than the root then make it root and call heapify for MH b) Else ignore it. O((n-m)*logm) 3) Finally, MH has m largest elements and root of the MH is the mth largest element.
On Aug 8, 3:57 pm, vijay goswami <[email protected]> wrote: > run bubble sort for m passes > > On Mon, Aug 8, 2011 at 4:02 PM, Nitin Nizhawan > <[email protected]>wrote: > > > > > > > > > Selection algorithm,http://en.wikipedia.org/wiki/Selection_algorithm > > > On Mon, Aug 8, 2011 at 3:59 PM, nick <[email protected]> wrote: > > >> how will you find the m'th maximum element in an unsorted array of > >> integers? > > >> -- > >> 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/-/aYU_PfGHiNkJ. > >> 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 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 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.
