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 <shrava...@gmail.com> 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 > <adorableyamin...@gmail.com>wrote: > >> partition the array using quick sort >> and find the kth smallest or largest number >> >> >> On Sep 6, 12:20 am, learner <nimish7andr...@gmail.com> wrote: >> > @Dave,All So Can Anyone Provide The Working Code in Linear Time for >> > the same ? >> > >> > Thanks >> > >> > On Sep 5, 6:41 pm, Dave <dave_and_da...@juno.com> 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 <monugoya...@gmail.com> 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 >> > > > <monugoya...@gmail.com>wrote: >> > >> > > > > PLEASE TELL HOW >> > >> > > > > On Sun, Sep 4, 2011 at 7:23 PM, sarath prasath < >> prasathsar...@gmail.com>wrote: >> > >> > > > >> another sol which i learned from my friend is >> > > > >> think of heap sort... >> > >> > > > >> On Sun, Sep 4, 2011 at 6:28 PM, learner < >> nimish7andr...@gmail.com> 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 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. >> > >> > > > >> -- >> > > > >> 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.-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 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. >> >> > -- > 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. > -- 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.
