mth largest element in array

Given an array of N elements . cud any of u suggest how to find the mth largest element where 1<m<=n

thankx

use the binary method
(i'll get back with more)

Try binary search/ linear search or any of the searching methods and then get the mth member

for binary search, u need to sort it first
sorting will cost 'n*log(n)' for unknown range of numbers, or cost 'n' with known range using bucket sort
once you have that just pick it out of the mth position in the array.

That's the best i can think of.
You will obviously need to inspect every element which will cost you 'n' and then get it, so with a known range of numbers this is the best you will get. And without a known range, 'nlogn' is still excellent!

Cheers

E'one's posted replies saying to use binary search and all.. but that wudnt really be reqd... sorting wud ensure that all elements fall in place .. jus accessing the mth element from the array would see me thro'.

Sorting is 1 of the ways i agree , but given n elements and
1<= m <=n why shud i sort elements upto m-1... when all i need is elements starting from m onwards sorted... I hope u are getting my point

no .. u need to check every element

for example getting the 3rd smallest element from a list
what if you added an element that is smaller than all in the list, and if u didnt check all elements (including the lsat one) then u'd have the 4th smallest instead of hte 3rd smallest

u need to sort EVERY element.

ok... i have been working in dis algo dis way... heap-sorting the elements... so for the 1st ele... the ele on d top of d heap is d answer...
but say i want the 3/4/5th ele... then ???

ahh .. my flatmate thought of a much better way than sorting!

-pick a pivot (as in quick sort)
-split up elements to
left side = element less than pivot
right side = elements more than pivot

then you would be ablt to decide which side to continue searching on for ur element

for avg case,you need to inspect
n + n/2 + n/4 + .......
which limits to 2n which is pretty ****ing excellent!

cheers

yogi,
are u asking me to apply quick sort algo??
iam still not clear what u'd written.. can u clarify plz

no don't use quick sort, just use the pivot idea from it

for example, say you hve the numbers
2,4,7,8,1,3,5,6
and you wanna find the 3rd largest

you pick a pivot, say (first+last)/2 = 4
then split into those less(or equal) and thos more
less_1 = 2,4,1,3
more_1 = 7,8,5,6
now you want 3rd largest so you only need to check the right (more_1) side since the 4 largest elements are there.

so do it again .. but with 7,8,5,6
pick pivot = (7+6)/2 = 6 (after rounding)

more_2 = 7,8
less_2 = 5,6

you want third largest, and cuz the more_2 is the two largest and the more_1 is the 4 largest, you'd do it again and look for the largest in less_2

you do this recursively splitting it in half each time.
so the avg cost will be n + n/2 + n/4 + .....
which limits to 2n in cost.

Cheers

thanks yogi !

Ummm...
I don't think yogi is lazy enough.

I am totally NOT dumping on your algorithm, but by the time you've done the grouping (into less and more groups) you could have been done finding the correct element.

I'll show you:
pick pivot (+1)
do comparisons with every element in the list (+n)
pick new pivot (+1)
re-compare etc.

Try a quicksort and index the mth largest element directly.
quicksort (+nlogn)
retrieve element (+1)

Also easier to implement since everyone on the planet's written a quicksort

-pb

haha .. I am lazy!! And I'll prove it!!

ur wrong ! - twice !
1. I am lazy!!


quicksort cost :
---------------
best : n
avg: nlogn
worst: n^2

mine:
-----
best: n (if u split it right first time)
avg: 2n = O(n)
worst = n^2

avg case is most often used and O(n) is better than O(nlogn)

QED: I am lazy!

offtopic: lazy_yoigi....u wrote those lines...therefore u r not lazy :P

OY!