+1 to piyush On Tue, Sep 6, 2011 at 11:15 PM, Piyush Grover <piyush4u.iit...@gmail.com>wrote:
> 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) > Tho piyushis 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. > -- 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.
