check the case 63 62 46 71 28 39 43 24 36 12
You have to find 3rd largest 62
your case you will miss 62 in your first iteration
On Wed, Sep 7, 2011 at 9:41 AM, Anup Ghatage ghat...@gmail.com wrote:
Here is another one. Pardon me if it goes by some other name.
Divide the array in K parts.
@Dave:
Can u pls provide the link for median of median algo in O(n) time ..
On Wed, Sep 7, 2011 at 11:44 AM, Karan Thakral karanthak...@gmail.comwrote:
check the case 63 62 46 71 28 39 43 24 36 12
You have to find 3rd largest 62
your case you will miss 62 in your first iteration
On
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:
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.comwrote:
partition the array using quick sort
and find the kth smallest or largest number
On Sep 6, 12:20 am, learner
@Yamini: The quicksort partitioning method will find the kth order
statistic in _average_ time O(n), but the worst cast time is O(n^2).
Getting O(n) worst cast behavior is more complicated. Shravan gives a
helpful link that describes the algorithm well.
Dave
On Sep 6, 9:23 am, yamini gupta
+1 to piyush
On Tue, Sep 6, 2011 at 11:15 PM, Piyush Grover piyush4u.iit...@gmail.comwrote:
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
@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,
find by sing median of median methods
--
*UTKARSH SRIVASTAV
CSE-3
B-Tech 3rd Year
@MNNIT ALLAHABAD*
--
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
@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
@dave:what if u have duplicate elements
Ashima
M.Sc.(Tech)Information Systems
4th year
BITS Pilani
Rajasthan
On Mon, Sep 5, 2011 at 7:11 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
@Ashima: I don't think duplicate elements cause any trouble. During
the pivoting pass, you find an element that is = the pivot on the
right side and one that is = the pivot on the left and swap them.
That allows elements equal to the pivot to be on both sides of the
pivot. So there is no problem
11 matches
Mail list logo
