June 30th, 2003, 12:33 AM
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
June 30th, 2003, 05:50 AM
use the binary method
(i'll get back with more)
June 30th, 2003, 08:39 AM
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 08:42 AM.
June 30th, 2003, 12:24 PM
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!
June 30th, 2003, 11:48 PM
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!
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
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.
thanks yogi !
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)
Try a quicksort and index the mth largest element directly.
retrieve element (+1)
Also easier to implement since everyone on the planet's written a quicksort
haha .. I am lazy!! And I'll prove it!!
ur wrong ! - twice !
1. I am lazy!!
quicksort cost :
best : n
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