finding median of 5 elements

the following question was asked in a recent microsoft interview

Given an unsorted array of size 5. How many minimum comparisons are needed to find the median? then he extended it for size n.

solution for 5 elements according to me is 6

1) use 3 comparisons to arrange elements in array such that a[1]<a[2] , a[4]<a[5] and a[1]<a[4]
a) compare a[1] and a[2] and swap if necessary
b) compare a[4] and a[5] and swap if necessary 
c) compare a[1] and a[4].if a[4] is smaller than a[1] , then swap a[1] wid a[4] and a[2] wid a[5]
2)if a[3]>a[2].if a[2]<a[4] median value = min(a[3],a[4]) else median value=min(a[2],a[5]) 
3)if a[3]<a[2].if a[3]>a[4] median value = min(a[3],a[5]) else median value=min(a[2],a[4]) 

can this be extended to n elements. if not how can we find median in n elements in O(n) besides quickselect

---

The Select algorithm divides the list into groups of five elements. (Left over elements are ignored for now.) Then, for each group of five, the median is calculated (an operation that can potentially be made very fast if the five values can be loaded into registers and compared - 6 comparisons min). Select is then called recursively on this sublist of n/5 elements to find their true median.

链接地址: http://www.djcxy.com/p/61254.html

上一篇: 强制JavaScript在浏览器重绘之前运行*（jsFiddle示例）

下一篇: 找到5个元素的中位数