Author |
Topic: Median of 5 (Read 37028 times) |
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender: 
Posts: 1001
|
 |
Median of 5
« on: Aug 25th, 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: 13730
|
|
Re: Median of 5
« Reply #1 on: Aug 25th, 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 25th, 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: 13730
|
|
Re: Median of 5
« Reply #3 on: Aug 25th, 2003, 12:51pm » |
Quote Modify
|
I think a tree would give more than six comparisons in worse-case scenarios.. Balancing the tree only helps a little, but worse-case I still get 8.
nifty AVL-tree applet
|
| « Last Edit: Aug 25th, 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 25th, 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 27th, 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 27th, 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 27th, 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 27th, 2003, 12:54pm by tohuvabohu » |
IP Logged |
|
|
|
wowbagger
Uberpuzzler
 
Gender:
Posts: 727
|
|
Re: Median of 5
« Reply #8 on: Aug 27th, 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 27th, 2003, 1:00pm by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
on Aug 27th, 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 27th, 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 27th, 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: 13730
|
|
Re: Median of 5
« Reply #11 on: Aug 28th, 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 28th, 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 28th, 2003, 8:54am » |
Quote Modify
|
on Aug 28th, 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: 13730
|
|
Re: Median of 5
« Reply #15 on: Aug 28th, 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 Merge-sort. 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 28th, 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 28th, 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 known-smaller 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 median-of-medians procedure, partitioning the numbers by the pivot, then choosing a new pivot in the remaining numbers. The reason they use the median-of-medians 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 second-smallest number, and then the second-second-smallest 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 28th, 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: 13730
|
|
Re: Median of 5
« Reply #18 on: Aug 28th, 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 30th, 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 30th, 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 1st, 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 9th, 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 7th, 2005, 6:26am » |
Quote Modify
 Remove
|
[color=Yellow][/color]
Give an algorithm to find the Median of 5 numbers in 6 comparisons
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print