Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

#1
June 29th, 2003, 11:33 PM
 me_no_xpert
Junior Member

Join Date: Jun 2003
Location: India
Posts: 19
Time spent in forums: < 1 sec
Reputation 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
June 30th, 2003, 04:50 AM
 heinrich
digital sinner

Join Date: Mar 2003
Location: sinner's land
Posts: 68
Time spent in forums: 4 h 37 m 30 sec
Reputation Power: 11
use the binary method
(i'll get back with more)

#3
June 30th, 2003, 07:39 AM
 mathurnitin
Registered User

Join Date: Jun 2003
Location: Bangalore, India
Posts: 13
Time spent in forums: 30 m 10 sec
Reputation 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
June 30th, 2003, 11:24 AM
 lazy_yogi
Contributing User

Join Date: Mar 2003
Posts: 325
Time spent in forums: 7 h 58 m 36 sec
Reputation Power: 11
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
June 30th, 2003, 10:48 PM
 me_no_xpert
Junior Member

Join Date: Jun 2003
Location: India
Posts: 19
Time spent in forums: < 1 sec
Reputation 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
June 30th, 2003, 11:05 PM
 lazy_yogi
Contributing User

Join Date: Mar 2003
Posts: 325
Time spent in forums: 7 h 58 m 36 sec
Reputation Power: 11
Quote:
 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
July 1st, 2003, 12:21 AM
 me_no_xpert
Junior Member

Join Date: Jun 2003
Location: India
Posts: 19
Time spent in forums: < 1 sec
Reputation 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
July 1st, 2003, 12:39 AM
 lazy_yogi
Contributing User

Join Date: Mar 2003
Posts: 325
Time spent in forums: 7 h 58 m 36 sec
Reputation Power: 11
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
July 1st, 2003, 05:42 AM
 me_no_xpert
Junior Member

Join Date: Jun 2003
Location: India
Posts: 19
Time spent in forums: < 1 sec
Reputation 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
July 1st, 2003, 05:51 AM
 lazy_yogi
Contributing User

Join Date: Mar 2003
Posts: 325
Time spent in forums: 7 h 58 m 36 sec
Reputation Power: 11
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
July 1st, 2003, 06:46 AM
 me_no_xpert
Junior Member

Join Date: Jun 2003
Location: India
Posts: 19
Time spent in forums: < 1 sec
Reputation Power: 0
thanks yogi !

#12
July 2nd, 2003, 04:41 PM
 palebear
Junior Member

Join Date: Jul 2003
Posts: 2
Time spent in forums: < 1 sec
Reputation 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
July 3rd, 2003, 06:33 AM
 lazy_yogi
Contributing User

Join Date: Mar 2003
Posts: 325
Time spent in forums: 7 h 58 m 36 sec
Reputation Power: 11
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
July 3rd, 2003, 07:22 AM
 heinrich
digital sinner

Join Date: Mar 2003
Location: sinner's land
Posts: 68
Time spent in forums: 4 h 37 m 30 sec
Reputation Power: 11
offtopic: lazy_yoigi....u wrote those lines...therefore u r not lazy :P

#15
July 3rd, 2003, 07:37 AM
 lazy_yogi
Contributing User

Join Date: Mar 2003
Posts: 325
Time spent in forums: 7 h 58 m 36 sec
Reputation Power: 11
OY!

 Viewing: Dev Shed Forums > Programming Languages - More > Software Design > mth largest element in array