1st and 2nd smallest and largest element

[BASHIR]

hi all,
hope u r fine,
i've tried too much in these 2 problems
if anyone have ideas, please share' em

1 - find the 2nd smallest element of an unsorted array in
( n + logbase2(n) - 1 ) comparisons

2 - find smallest and largest elements of an unsorted array in
( (3/2) * n - 2 ) comparisons

THANKS IN ADVANCE

[Yves M]

So what have you tried?

[BASHIR]

hi all again ,
finally i answered the 2 problems ,
here it's for those who r interestd


1 - for simplicity suppose number of element is even , group it to couples , compare each couple & promote the smaller to next stage , ( like in soccer tournaments ) , each two promoted will be coupled again, and compared ... etc till reaching the smallset , we till now have made [ n - 1] comaprisons , (u can imagine it as a binary tree build from base to its root 'the smallest') now to find the samallest elements we have to pass back over the branch of the smallest element and choose the smallest element that was disqualified ( not promoted when meeting the samllest) , this will be done in [ logbase2 (n) - 1 ] comaprisons
so the total solution = n - 1 + logbase2(n) - 1 = n + logbase2(n) - 2
p.s : this is better than the requirement as its required to be [ n + logbase2(n) - 1 ] comparisons
numerical example :
suppose array={ 2 , 13 , 9 , 1 , 8 , 5 , 4 , 3 , 0 , 6 , 12 , 10 , -1 , 11 , 7 , 14 }
coupling it { (2 ,13) , (9,1) , (8,5) , (4,3) , (0,6) , (12,10) , (-1,11) , (7,14) }
promoting { (2,1) , (5,4) , (0,10) , (-1,7) }
promoting { (1,4) , (0,-1) }
promoting { (1,-1) }
promoting { -1 } the samllest
if u haven't notice we have made it in 15 comparisons = n - 1
to find the second smallest don't think it's the '1' that reaches the final with '-1' going back collecting array of all oponents that the smallest(-1) met = {1 , 0 , 7 , 11}
we need 3 comparisons only to find the smallest in this set , which = logbase2(n) - 1


2 - for simplicity suppose number of element is even , group it to couples , compare each couple & put the smaller of each couple in an array called (smaller_terms) and put the greater of each couple in an array called (greater_terms) , we have till now ,to construct the 2 arrays (smaller terms) and (greater terms), made n/2 comparisons , each array of these 2 has n/2 terms , to find the smallest element we need to search the smaller_terms which will take n/2 - 1 comparisons , the same will be done to find the greatest element we will make a search in the greater_terms in n/2 - 1 comparisons
So total comparisons = ( n/2 ) + ( n/2 - 1 ) + ( n/2 - 1 ) = (3/2)*n - 2
numerical example :
suppose an array { 2 , 13 , 9 , 1 , 8 , 5 , 4 , 3 }
coupling it { (2 ,13) , (9,1) , (8,5) , (4,3) }
after 1st comparison (2,13) =>
smaller_terms = {2} & greater_terms = {13}
after 2nd comparison (9,1) =>
smaller_terms = {2,1} & greater_terms = {13,9}
after 3rd comparison (8,5) =>
smaller_terms = {2,1,5} & greater_terms = {13,9,8}
after 4th comparison (4,3) =>
smaller_terms = {2,1,5,3} & greater_terms = {13,9,8,4}
smallest by searching {2,1,5,3} in 3 comparisons = {1}
greatest by searching {13,9,8,4} in 3 comparisons = {13}
so total is 4 + 3 + 3 comp.s = 10 comp.s = (3/2)*8 - 2


sorry for long explanation
hope i'm not wrong in the solution : )
thanks Yves M
if anyone find 'em good solutions , rate this post


PS : VIVA EGYPTIAN BRAINS

[Yves M]

1. Yeah, seems allright. You do need the n + logbase2(n) - 1 comparisons though if the number of elements is odd.

2. Again correct as far as I can see.

Thanks for posting your solution.