Найти медиану из 5 элементов

Question

Следующий вопрос был задан в недавнем интервью Microsoft

Учитывая несортированный массив размера 5. Сколько минимальных сравнений необходимо, чтобы найти медиану? Затем он расширил его на размер п.

решение для 5 элементов по мне 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]) 

это может быть расширено до п элементов. если нет, то как мы можем найти медиану в n элементах в O(n), кроме быстрого выбора

Answer 1

Алгоритм выбора делит список на группы из пяти элементов. (Оставшиеся элементы на данный момент игнорируются.) Затем для каждой группы из пяти вычисляется медиана (операция, которая потенциально может быть выполнена очень быстро, если пять значений можно загрузить в регистры и сравнить - 6 сравнений мин). Затем в этом подсписке из n/5 элементов вызывается метод рекурсивного выбора, чтобы найти их истинную медиану.