Google for BFPRT (Blum, Floyd, Pratt, Rivest, Tarjan). This is an algorithm for finding the median in O(n) but it can be simply modified to find the k-th smallest/largest element.
Regards, Daniel Influential Deepu wrote: >I have been thinking on this problem for quite some time now, but am >not able to get a linear time algo for the same. > >Can nybody help. > > >> > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---