@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.
