Median of median algorithm will do the job...Its worst case performance
analysis is O(n).
The algorithm can be found in wikipedia (search for selection algorithm) but
it is sometimes found difficult to code for it..
I hope following pseudocode will do the job. I am doing it for general Kth
smallest element
*int select(int A[],int first, int last, int K) {*
* n = last - first + 1; /* number of elements*/
if( n < = 10 )
{
/* For Small n */
sort A;
return Kth smallest element;
}
else
{
numGroups = (n + 4 ) / 5; /* integer division, rounding up */
int *S = new int[newgroups];
for i = 0 to numGroups-1
{
shift = i*5;
/* A[first+shift] is the start of the group, A[first+shift+4] is end of
group */
find median of A[first+shift .. first+shift+4] and store it into
another array S[i]; /*6 comparisons required*/
}
int element = select(S , 0, numGroups-1, numGroups/2);
int pivot_index = findelement (A,first,last,element); /*find the
index of the element*/
int M = partition(A, first, last, pivot_index); /*returns the
position of Mth largest element/*
if ((M+1) == K) {
return A[M]
}
else if ((M+1) > K) {
return (select(A, first, M-1, K));
}
else
{
return (select(A, M+1, last, K-M-1));
}
}
}
*
On Mon, Jun 6, 2011 at 12:25 PM, Vipul Kumar <[email protected]> wrote:
> "This is called finding the k-th order statistic" study the topic from
> cormen its there.
>
> On Mon, Jun 6, 2011 at 12:15 PM, the coder <[email protected]> wrote:
> > hi friendz
> >
> > given an array how to find the k th largest element in O(N)
> > complexity.
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> [email protected].
> > 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=100000655377926 *
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
