wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Median of 5
        
(Message started by: TenaliRaman on Aug 25^th, 2003, 8:58am)

Title: Median of 5
Post by TenaliRaman on Aug 25^th, 2003, 8:58am

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

Title: Re: Median of 5
Post by towr on Aug 25^th, 2003, 9:38am

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

still not 6 though

Title: Re: Median of 5
Post by TenaliRaman on Aug 25^th, 2003, 10:43am

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.

Title: Re: Median of 5
Post by towr on Aug 25^th, 2003, 12:51pm

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 (http://www.seanet.com/users/arsen/avltree.html)

Title: Re: Median of 5
Post by James Fingas on Aug 25^th, 2003, 2:00pm

That was fairly tricky:

[hide]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].[/hide]

I don't know how this scales for other values of N.

Title: Re: Median of 5
Post by TenaliRaman on Aug 27^th, 2003, 11:38am

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

Title: Re: Median of 5
Post by Sir Col on Aug 27^th, 2003, 12:12pm

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.

Title: Re: Median of 5
Post by tohuvabohu on Aug 27^th, 2003, 12:49pm

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

Title: Re: Median of 5
Post by wowbagger on Aug 27^th, 2003, 12:55pm

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.

Title: Re: Median of 5
Post by James Fingas on Aug 27^th, 2003, 1:29pm

on 08/27/03 at 11:38:18, 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]

Title: Re: Median of 5
Post by Sir Col on Aug 27^th, 2003, 5:17pm

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

Title: Re: Median of 5
Post by towr on Aug 28^th, 2003, 2:22am

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

Title: Re: Median of 5
Post by TenaliRaman on Aug 28^th, 2003, 7:56am

Thanks all !!!!
The diagram helped a lllottt !! thanks james !! :)

TR

Title: Re: Median of 5
Post by James Fingas on Aug 28^th, 2003, 8:54am

on 08/28/03 at 02:22:09, 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.

Title: Re: Median of 5
Post by towr on Aug 28^th, 2003, 9:35am

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

Title: Re: Median of 5
Post by towr on Aug 28^th, 2003, 9:52am

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

Title: Re: Median of 5
Post by James Fingas on Aug 28^th, 2003, 10:42am

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.

Title: Re: Median of 5
Post by James Fingas on Aug 28^th, 2003, 12:05pm

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.

Title: Re: Median of 5
Post by towr on Aug 28^th, 2003, 12:52pm

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.

Title: Re: Median of 5
Post by TenaliRaman on Aug 30^th, 2003, 12:04am

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.

Title: Re: Median of 5
Post by DH on Aug 30^th, 2003, 6:34am

on 08/30/03 at 00:04:06, 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.

Title: Re: Median of 5
Post by TenaliRaman on Sep 1^st, 2003, 5:07am

Thanks for the reinforcement DH!!

Title: Re: Median of 5
Post by NoNamePlease on Jan 12^th, 2004, 7:12pm

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

Title: Re: Median of 5
Post by Azereal on Dec 9^th, 2004, 9:42pm

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

Title: algorithm find the Median 5 numbers in 6 comparisn
Post by ramavtar on Jan 7^th, 2005, 6:26am

Give an algorithm to find the Median of 5 numbers in 6 comparisons

Title: Re: Median of 5
Post by Jon Anderson on Feb 4^th, 2005, 1:40pm

Just so you know,the median of median method is used to find the pivot for solving the selection problem, not for doing a quicksort. The selection problem is that of finding the kth smallest element in an unsorted list of n elements. The best approach is to apply the quicksort algorithm. If the pivot lands in spot k, then you are done. Otherwise, you have to run the algorithm on whichever half of the list k happens to be in, not both as in the quicksort. It can be shown that by using the median-of-medians approach, the worst case scenario is still solved in linear time. (22n by comparisions)