### Thread: mth largest element in array

Page 1 of 2 12 Last
1. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Jun 2003
Location
India
Posts
19
Rep Power
0

#### 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
2. use the binary method
(i'll get back with more)
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jun 2003
Location
Bangalore, India
Posts
13
Rep Power
0

Try binary search/ linear search or any of the searching methods and then get the mth member
Last edited by mathurnitin; June 30th, 2003 at 07:42 AM.
4. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Mar 2003
Posts
325
Rep Power
12
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
5. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Jun 2003
Location
India
Posts
19
Rep Power
0
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
6. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Mar 2003
Posts
325
Rep Power
12
Originally posted by me_no_xpert
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.
7. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Jun 2003
Location
India
Posts
19
Rep Power
0
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 ???
8. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Mar 2003
Posts
325
Rep Power
12
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
9. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Jun 2003
Location
India
Posts
19
Rep Power
0
yogi,
are u asking me to apply quick sort algo??
iam still not clear what u'd written.. can u clarify plz
10. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Mar 2003
Posts
325
Rep Power
12
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
11. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Jun 2003
Location
India
Posts
19
Rep Power
0
thanks yogi !
12. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Jul 2003
Location
Posts
2
Rep Power
0
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
13. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Mar 2003
Posts
325
Rep Power
12
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!
14. offtopic: lazy_yoigi....u wrote those lines...therefore u r not lazy :P
15. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Mar 2003
Posts
325
Rep Power
12
OY!
Page 1 of 2 12 Last