@Piyush: You are correct, but the more complicated median-of-median algorithms can find the kth order statistic in O(n), independent of k. Thus, the median, which is the n/2th order statistic, can be found in O(n), whereas the heap algorithm will find the median in O(n log n).
Dave On Sep 6, 12:45 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) > 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/... > > > 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.-Hidequotedtext - > > >> > > > - 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.- Hide quoted 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.
