wu :: forums « wu :: forums - Median of 5 » Welcome, Guest. Please Login or Register. Nov 27th, 2015, 2:01am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    cs (Moderators: Eigenray, william wu, Grimbal, SMQ, Icarus, towr, ThudnBlunder)    Median of 5 « Previous topic | Next topic »
 Pages: 1 2 Reply Notify of replies Send Topic Print
 Author Topic: Median of 5  (Read 21792 times)
TenaliRaman
Uberpuzzler

I am no special. I am only passionately curious.

Gender:
Posts: 999
 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: 13276
 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: 999
 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: 13276
 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

TenaliRaman
Uberpuzzler

I am no special. I am only passionately curious.

Gender:
Posts: 999
 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

James Fingas
Uberpuzzler

Gender:
Posts: 949
 Re: Median of 5   median_of_five.gif « Reply #9 on: Aug 27th, 2003, 1:29pm » Quote Modify

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 ...

darn! too late. But my graph is still good![/edit]
 « Last Edit: Aug 27th, 2003, 1:33pm by James Fingas » IP Logged

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: 13276
 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: 999
 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

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13276
 Re: Median of 5   « Reply #14 on: Aug 28th, 2003, 9:35am » Quote Modify

Well I think the answer should be somewhere on http://www-math.mit.edu/18.310/finding_median.html but I have yet to sit down and actually devote some braincapacity to understanding it all..
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13276
 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

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

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13276
 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: 999
 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

 Re: Median of 5   « Reply #20 on: Aug 30th, 2003, 6:34am » Quote Modify Remove

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: 999
 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
Guest

 Re: Median of 5   « Reply #22 on: Jan 12th, 2004, 7:12pm » Quote Modify Remove

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
 Pages: 1 2 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »