this can be done using heap tree data structure. -create a max heap tree of first k elements (for finding kth min) -keep on adding elements in the heap if the root element is greater than the current element, remove root element and insert the current element in the tree once done with n elements the root element will give the kth min element. Time complexity: O(nlogk) This method is very much effective for k << n (when k is a constant)
Same can be done for kth max. On Tue, Sep 6, 2011 at 9:00 PM, Shravan Kumar <[email protected]> wrote: > > http://jonah.cs.elon.edu/sduvall2/courses/csc331/2006spring/Lectures/Order_statistics.ppt > > > On Tue, Sep 6, 2011 at 7:53 PM, yamini gupta > <[email protected]>wrote: > >> partition the array using quick sort >> and find the kth smallest or largest number >> >> >> On Sep 6, 12:20 am, learner <[email protected]> wrote: >> > @Dave,All So Can Anyone Provide The Working Code in Linear Time for >> > the same ? >> > >> > Thanks >> > >> > On Sep 5, 6:41 pm, Dave <[email protected]> wrote: >> > >> > >> > >> > >> > >> > >> > >> > > @Sachin: Correct: in one quicksort pivoting pass, the array is >> > > rearranged so that the pivot element is put in the correct spot, with >> > > larger elements on the right and smaller ones on the left. Now, if the >> > > pivot, a[p], is at location k, i.e. p = k, then you are done. If not, >> > > do another quicksort on the correct side of p; i.e., either on a[0] to >> > > a[p-1] or on a[p+1] to a[n-1], depending on whether k is less than p >> > > or greater than p. >> > >> > > Dave >> > >> > > On Sep 5, 1:27 am, sachin goyal <[email protected]> wrote: >> > >> > > > PLEASE TELL ME HOW WE CAN USE QUICK SORT TO FIND THE ELEMENT >> > > > BECAUSE IN QUICK SORT ONE ELEMENT IN SHIFT IN ITS RIGHT POSITION ALL >> LEFTS >> > > > ARE SMALLER AND ALL RIGHT ARE BIG >> > >> > > > On Mon, Sep 5, 2011 at POSIT11:55 AM, sachin goyal >> > > > <[email protected]>wrote: >> > >> > > > > PLEASE TELL HOW >> > >> > > > > On Sun, Sep 4, 2011 at 7:23 PM, sarath prasath < >> [email protected]>wrote: >> > >> > > > >> another sol which i learned from my friend is >> > > > >> think of heap sort... >> > >> > > > >> On Sun, Sep 4, 2011 at 6:28 PM, learner < >> [email protected]> wrote: >> > >> > > > >>> something I Know using quick sort randomization function we can >> find >> > > > >>> kt smallest/largest in unsorted array , but i am not able to >> write >> > > > >>> code , please help me in this and provide the code for the >> same.? >> > >> > > > >>> Thanks >> > > > >>> Nimish K. >> > > > >>> 1st Year >> > > > >>> IITR >> > >> > > > >>> -- >> > > > >>> 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.-Hidequoted 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 [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.
