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.
