You can use algorithim for finding median in unsorted array.
int medianofUnsortedArray(int a[], int low, int high, int rank){
int l, h, pivot;
int temp;
pivot = l = low;
h = high;
if(l<=h){
while(l<h){
while(a[l] <= a[pivot]) l++;
while(a[h] > a[pivot]) h--;
temp = a[h];
a[h] = a[l];
a[l] = temp;
}
temp = a[h];
a[h] = a[pivot];
a[pivot] = temp;
}
if(rank < h){
medianofUnsortedArray(a,low,h-1,rank);
}else if(rank > h){
medianofUnsortedArray(a,h+1,high,rank);
}else{
return a[h];
}
}
/*
1.
pivot = l
a[piv] if(a[pivot]>p[l])<------h
| |
- - - - - - - - ------- - -- - - - - - - - - -
|
l++ ------> if(a[pivot]>p[l])
2.
l=h
+ - - - - - - - - - - - - - - = - - - - -
3. swap(a[pivot],a[h])
<---------------------------+
| rank |
= - - - - - - - - # - --- - - + - - - - -
| |
+------------------------->
*/
On Thu, Jul 22, 2010 at 10:35 PM, jalaj jaiswal
<[email protected]> wrote:
>
> use selection algorithm ....
>
> On Thu, Jul 22, 2010 at 9:53 PM, Tech Id <[email protected]> wrote:
>>
>> Write an algo (in less than O(n^2)) to find k-th maximum in an
>> unsorted array of integers.
>>
>> --
>> 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.
>>
>
>
>
> --
> With Regards,
> Jalaj Jaiswal
> +919026283397
> B.TECH IT
> IIIT ALLAHABAD
>
> --
> 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.
--
Regards,
Shafi Ahmad
The difficult we do immediately, the impossible takes a little longer....US Army
--
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.
