Thanks subramania.. It is very nice explanation.. [?] On Mon, Jun 6, 2011 at 8:33 PM, subramania jeeva <subramaniaje...@gmail.com>wrote:
> @Gaurav Aggarwal > Obviously O(n^2) worst case if we use ordinary quick sort with slight > modification(Best case O(n))... > But quick sort can also be done by taking median as element for partition > instead of taking first or last element which will take O(nlgn) worst case > complexity... > But to do the given problem median of median algorithm is best.. It will > take O(n) in worst case... > > 1. Divide the n elements of input into n/5 groups > 2. Find median of each group by insertion sort(performs well for small > inputs) and pick the median for each each group. > 3. Repeat steps (1) and (2) repeatedly to find a single median > 4.partition the array using that median. such that k elements are in lower > partition and n-k elements are in higher side of partition.(use the > partition insuch a way that smallest elements are on higher side of > partition and largest elements are on lower side of partition) > > 5. If index i==k(ith largest element) then return a[i].. else recurse steps > 1 to 5 such that (if i>k then use k to r) (else use p to k)(p is the > starting index and r is ending index).. > > I hope It explains the code given by piyush sinha.. > > > > > > > > > > Cheers > ~ Jeeva ~ > > > > -- > 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?hl=en. > -- Gaurav Aggarwal SCJP -- 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?hl=en.
<<328.png>>
