Author 
Topic: Median of 5 (Read 34267 times) 

TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001


Median of 5
« on: Aug 25^{th}, 2003, 8:58am » 
Quote Modify

this must be a very old thingy but still i am not able to do it ... Find the median of 5 elements using just 6 comparisons. The closest i think i got was 12 comparisons


IP Logged 
Self discovery comes when a man measures himself against an obstacle  Antoine de Saint Exupery



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13729


Re: Median of 5
« Reply #1 on: Aug 25^{th}, 2003, 9:38am » 
Quote Modify

you can order them with 10 or less comparisons.. (quicksort) And once ordered you can easily pick the middle. still not 6 though


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001


Re: Median of 5
« Reply #2 on: Aug 25^{th}, 2003, 10:43am » 
Quote Modify

hmm how about an AVL tree? It seems to give 6 comparisons . But then there must be a better way .... i don't think i would build an AVL tree just to find a median of 5 numbers.


IP Logged 
Self discovery comes when a man measures himself against an obstacle  Antoine de Saint Exupery



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13729


Re: Median of 5
« Reply #3 on: Aug 25^{th}, 2003, 12:51pm » 
Quote Modify

I think a tree would give more than six comparisons in worsecase scenarios.. Balancing the tree only helps a little, but worsecase I still get 8. nifty AVLtree applet

« Last Edit: Aug 25^{th}, 2003, 12:54pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Median of 5
« Reply #4 on: Aug 25^{th}, 2003, 2:00pm » 
Quote Modify

That was fairly tricky: 1) Put the numbers in an array. 2) Use three comparisons and shuffle around the numbers so that a[1] < a[2], a[4] < a[5], and a[1] < a[4]. 3) If a[3] > a[2], then the problem is fairly easy. If a[2] < a[4], the median value is the smaller of a[3] and a[4]. If not, the median value is the smaller of a[2] and a[5]. 4) So a[3] < a[2]. If a[3] > a[4], then the solution is the smaller of a[3] and a[5]. Otherwise, the solution is the smaller of a[2] and a[4]. I don't know how this scales for other values of N.


IP Logged 
Doc, I'm addicted to advice! What should I do?



TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001


Re: Median of 5
« Reply #5 on: Aug 27^{th}, 2003, 11:38am » 
Quote Modify

James, i have been at your algo for two days ... but i don't seem to understand it pretty well particularly i have been trying to find the median of 5,4,3,2,1. Step 1 : a[1]=5 a[2]=4 a[3]=3 a[4]=2 a[5]=1 Step 2 : a[1]=1 a[2]=5 a[3]=3 a[4]=2 a[5]=4 By Step 3 : median is 2


IP Logged 
Self discovery comes when a man measures himself against an obstacle  Antoine de Saint Exupery



Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825


Re: Median of 5
« Reply #6 on: Aug 27^{th}, 2003, 12:12pm » 
Quote Modify

I don't think this can be solved for EVERY possible configuration of 5 elements. Regardless of method: selection, bubble, or insertion, it requires 10 comparisons to do a complete sort for every possible configuration. As we only need to sort the first 3 elements, a selection sort of a[1]a[2], a[1]a[3], a[1]a[4], a[1]a[5], a[2]a[3], a[2]a[4], a[2]a[5], a[3]a[4], a[3]a[5], omitting the last a[4]a[5], would solve the problem. A bubble sort requires all ten iterations, as the last comparison puts the middle element in place. And whereas insertion sorts can be the most efficient for random lists, it would still require all ten comparisons to be certain. In other words, I believe that the minimum number of comparisons to sort the first 3 out of 5 elements is 9, and that would require a selection sort.


IP Logged 
mathschallenge.net / projecteuler.net



tohuvabohu
Junior Member
Gender:
Posts: 102


Re: Median of 5
« Reply #7 on: Aug 27^{th}, 2003, 12:49pm » 
Quote Modify

It looks to me like James' method works. In James' method you compare and switch (if necessary) a and b: you compare and switch d and e you compare a and d and if d is lower you switch both pairs so your equations don't get messed up. So the order becomes decab. So if the starting order was 54321, it becomes 45321, then 45312, then 12345. b<d, c<d, so it's 3. So after the first 3 comparisons the only possible orders are: (where c>b) 12345 12435 12534 : 13425 13524 14523 15423 (and where b>c) 13245 14235 15234 23145 24135 25134 : 14325 15324 Comparison five splits up the first group where I put the colon. In the first group the median is the smaller of c and d. In the second it's the smaller of b and e. Comparison five splits the second group at the colon. In the first group the median is the smaller of b and d. In the second it's the smaller of c and e

« Last Edit: Aug 27^{th}, 2003, 12:54pm by tohuvabohu » 
IP Logged 



wowbagger
Uberpuzzler
Gender:
Posts: 727


Re: Median of 5
« Reply #8 on: Aug 27^{th}, 2003, 12:55pm » 
Quote Modify

Quote:In other words, I believe that the minimum number of comparisons to sort the first 3 out of 5 elements is 9, and that would require a selection sort. 
 But we don't have to actually sort everything. When I first read this riddle, I was sure I've already encountered it in an exercise (long time ago). Of course, I couldn't remember the solution. Now that I've found it, I can assure you it does work with only six comparisons. I see that it is almost exactly the same as James's solution (now that I've read his). A proposal that might make it easier: visualize which variables you have already compared in a graph.

« Last Edit: Aug 27^{th}, 2003, 1:00pm by wowbagger » 
IP Logged 
"You're a jerk, <your surname>!"



James Fingas
Uberpuzzler
Gender:
Posts: 949

on Aug 27^{th}, 2003, 11:38am, TenaliRaman wrote: Step 1 : a[1]=5 a[2]=4 a[3]=3 a[4]=2 a[5]=1 Step 2 : a[1]=1 a[2]=5 a[3]=3 a[4]=2 a[5]=4 By Step 3 : median is 2 
 It looks like step 2 went okay. In step 3, we compare a[2] and a[3]. Since a[3]<a[2], we go to step 4. Since a[3]>a[4], then the median is the smaller of a[3] and a[5], which is a[3]. Seems right to me ... [edit]darn! too late. But my graph is still good![/edit]

« Last Edit: Aug 27^{th}, 2003, 1:33pm by James Fingas » 
IP Logged 
Doc, I'm addicted to advice! What should I do?



Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825


Re: Median of 5
« Reply #10 on: Aug 27^{th}, 2003, 5:17pm » 
Quote Modify

Who would have thought it... it seems to defy common sense belief. Thanks for the great diagram, James; it really helped me visualise the process.


IP Logged 
mathschallenge.net / projecteuler.net



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13729


Re: Median of 5
« Reply #11 on: Aug 28^{th}, 2003, 2:22am » 
Quote Modify

you can also order 5 elements in just 8 comparisons (obvious when you have the median in 6 and know which two are higher, and which two are lower) Also, it does in a way apply to N > 5 as well. There is an upper limit linear to the number of elements (sorting it would give an NlogN upper limit).


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001


Re: Median of 5
« Reply #12 on: Aug 28^{th}, 2003, 7:56am » 
Quote Modify

Thanks all !!!! The diagram helped a lllottt !! thanks james !! TR


IP Logged 
Self discovery comes when a man measures himself against an obstacle  Antoine de Saint Exupery



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Median of 5
« Reply #13 on: Aug 28^{th}, 2003, 8:54am » 
Quote Modify

on Aug 28^{th}, 2003, 2:22am, towr wrote:Also, it does in a way apply to N > 5 as well. There is an upper limit linear to the number of elements (sorting it would give an NlogN upper limit). 
 That's interesting. Is there a simple way to describe the strategy? Maybe some way to visualize it in terms of graphs? I seem to recall that there is a working algorithm out there. This seems like a good way to make QuickSort better (already been done?) It is obvious that you can find the smallest or largest elements in O(N) compares, but the median is not nearly as easy.


IP Logged 
Doc, I'm addicted to advice! What should I do?



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13729


Re: Median of 5
« Reply #15 on: Aug 28^{th}, 2003, 9:52am » 
Quote Modify

btw Quicksort is a randomized algorithm, with worsecase n^2. There is also a guaranteed N*log(N) time sorting algorithm called Mergesort. But the average running time of quicksort has a lower constant and is thus on average (much) faster. The same goes for this problem, there is a randomized algorithm that has an average linear running time which is smaller than the average running time of the deterministic linear algorithm (which is also more complex).

« Last Edit: Aug 28^{th}, 2003, 9:55am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Median of 5
« Reply #16 on: Aug 28^{th}, 2003, 10:42am » 
Quote Modify

The process in the article is fairly simple, but I sincerely doubt it is anywhere near optimal. Here's a brief rundown: 1) They divide the numbers into groups of 5, and sort each group, finding its median (ha! wasteful!). 2) The make a list of all the medians, and find the median of that list. 3) The compare the median of medians to all N numbers (not exactly, but same effect), finding its exact rank, thereby seeing if it's larger or smaller than the true median. If it's larger, they eliminate all numbers they know are larger (at least 3N/10). If it's smaller, they eliminate all knownsmaller numbers. 4) The redivide the numbers into new groups of 5 where necessary (again, using many more comparisons than necessary). 5) Rinse, repeat. Note that they're not searching for the median of the remaining numbers this time. Basically, they're choosing a pivot through a complicated medianofmedians procedure, partitioning the numbers by the pivot, then choosing a new pivot in the remaining numbers. The reason they use the medianofmedians method is that it allows them to guarantee that they'll be able to eliminate 3/10 of the numbers each time. Their bound is about 10N, but I think they'll almost always use this exact amount. There seems to be little chance of their method terminating early. I don't understand the part about searching for the secondsmallest number, and then the secondsecondsmallest number. I think they might be talking about using a heap ... But then you're just sorting half the numbers.


IP Logged 
Doc, I'm addicted to advice! What should I do?



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Median of 5
« Reply #17 on: Aug 28^{th}, 2003, 12:05pm » 
Quote Modify

This is interesting ... you can sort 5 items using only 7 comparisons (obviously the minimum since 5! = 120). But you can't do so if the first six are used to find the median.


IP Logged 
Doc, I'm addicted to advice! What should I do?



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13729


Re: Median of 5
« Reply #18 on: Aug 28^{th}, 2003, 12:52pm » 
Quote Modify

Well, most of the pages I can find on the subject describe the same algorithm, so it'll probably be the simplest linear algorithm or something, if not the most efficient. Of course for any given N there is a certain decision tree that will give the most efficient search, but I don't think that would be easy to generalize. (Nor easy to build for a specific large N) Either eway I think randomized is the way to go, since it's generally much faster on average anyway, though it's nice to know there's a deterministic linear algorithm.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001


Re: Median of 5
« Reply #19 on: Aug 30^{th}, 2003, 12:04am » 
Quote Modify

for large n,i think heap sort would do better than most sort when comparing the overheads reqd for other sorts.also heap sort is O(n log n) for almost all cases. As for the algo in the site given, it seems to find an almost optimal median in linear time and try to avoid quick sort from going into worst case.


IP Logged 
Self discovery comes when a man measures himself against an obstacle  Antoine de Saint Exupery



DH
Guest

on Aug 30^{th}, 2003, 12:04am, TenaliRaman wrote:for large n,i think heap sort would do better than most sort when comparing the overheads reqd for other sorts.also heap sort is O(n log n) for almost all cases. 
 Heap sort is O(n*log n) for ALL cases.


IP Logged 



TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001


Re: Median of 5
« Reply #21 on: Sep 1^{st}, 2003, 5:07am » 
Quote Modify

Thanks for the reinforcement DH!!


IP Logged 
Self discovery comes when a man measures himself against an obstacle  Antoine de Saint Exupery



NoNamePlease
Guest

I tried doing a (nearly) full search of the decision tree to find out the minimum number of comparisons required to find a median for various N. That (predictably, I guess) turned out to be a very hard task even for small N, because the tree branches out too fast. Anyway, for N=6, the minimum number of comparisons is also 6, for N=7 it is 10. One curious thing I found out playing with the program for N=6: at first I thought it safe to seed it with the initial state a0>a1, a2>a3, a4>a5. It turnes out that from this state you need 4 comparisons to find the median. That gives the total of 4+3=7. OTOH, from the minimalistic state a0>a1 you need 5 comparisons. (I should probably also mention that for even N if I find either of the two middle elements I consider the job done, rather than going for a fixed one.) So here is the table: N  min cmps + 2  0 3  3 4  3 5  6 6  6 7  10 >7 ?? Please post if you can provide any references to this problem (other than what was cited by towr).


IP Logged 



Azereal
Newbie
Posts: 1


Re: Median of 5
« Reply #23 on: Dec 9^{th}, 2004, 9:42pm » 
Quote Modify

Well I was posed this problem in one of my assignments and I turned to this forum for help but no help was here. I eventually found out how to do it. 1. Start a mergesort with the first 4 elements and order each pair (2 comparisons) 2. Compare the two lower ones of each pair and eliminate the lowest one from the possibilities (3 comparisons) 3. Add in the 5th number set aside to the number without a pair and compare the two (4 comparisons) 4. Compare the two lowest of the two new pairs and eliminate the lower one (5 comparisons) 5. Compare the one by itself and the lower of the last pair and the lower number is the median The possible median is within the parentesis (54321) 5:4 3:2 2 comparisons (4<5 2<3 1) 4:2 3 comparisons 2(4<5 3 1) 1:3 4 comparisons 2(4<5 1<3) 4:1 5 comparisons 1,2(4<5 3) 4:3 6 comparisons 1,2(3)4,5 Three is the median


IP Logged 



ramavtar
Guest


algorithm find the Median 5 numbers in 6 comparisn
« Reply #24 on: Jan 7^{th}, 2005, 6:26am » 
Quote Modify
Remove

[color=Yellow][/color] Give an algorithm to find the Median of 5 numbers in 6 comparisons


IP Logged 



