Медиана семи чисел

Алгоритм поиска медианы семи чисел:
1. Разбиваем первые шесть чисел на пары и упорядочиваем каждую по возрастанию. На это уйдёт 3 сравнения.
2. Если максимум второй пары больше максимума третьей меняем их меcтами ( 1 сравнение ).
3. Если максимум первой пары больше максимума второй переходим к пункту 9 ( 1 сравнение ).
4. В этом случае максимум третьей пары больше пяти чисел и медианой быть не может, поэтому его отбрасываем и делаем новую пару с седьмым числом ( 1 сравнение ).
5. Если максимум третьей пары больше максимума первой переходим к пункту 8 ( 1 сравнение ).
6. Отбрасываем максимум второй пары - он больше пяти чисел и минимум третьей пары - он меньше 3-х чисел. Если минимум второй пары больше максимума третьей пары ( 1 сравнение ) переходим к пункту 7. Иначе медианой будет больший из двух чисел ( 1 сравнение ) - минимум первой пары и максимума третьей. Конец.
7. В этом случае остаются три числа и одно сравнение. Чтобы определить их медиану понадобится ещё одно или два сравнения. Конец.
8. В этом случае минимум первой пары меньше трёх чисел, поэтому медианой быть не может. Сравниваем минимумы третьей и второй пары ( 1 сравнение ). После этого отбрасываем ещё два числа. Останется три и мы можем найти их медиану добавив одно или два сравнения. Конец.
9. Если максимум второй пары больше седьмого числа переходим к пункту 11 ( 1 сравнение ).
10. В этом случае минимум второй пары меньше 4-х чисел, поэтому медианой быть не может. Сравниваем минимумы первой и третьей пары ( 1 сравнение ). Если меньше минимум первой пары, то отбрасываем максимум третьей иначе наоборот. Останется пять чисел и четыре сравнения для которых нужно найти медиану. На это понадобится 2 или 3 сравнения. Конец.
11. В этом случае отбрасываем максимумы первой и третьей пар, т.к. они больше 4-х чисел. Сравниваем минимумы первой и третьей пары, а затем полученный максимум с максимумом второй пары ( 2 сравнения ). Если полученный максимум меньше переходим пункту 12. Иначе отбрасываем этот максимум т.к. он больше всех оставшихся чисел, а также минимум второй пары и седьмое число. Из оставшихся двух чисел медианой будет большее ( 1 сравнение ). Конец.
12. В этом случае отбрасываем максимум второй пары и минимум новой пары. Из трёх оставшихся чисел медианой будет большее ( 2 сравнения ). Конец.

В лучшем случае медиана будет найдена за 9 сравнений, в худшем - за 10. Если рассмотреть все 7! = 5040 перестановок 7 чисел, то получим следующую статистику:

		 9 - 2272
		10 - 2832

В среднем получается 9.549 сравнений.

Алгоритм реализован в виде шаблона-функции:

template<class T> inline T _median7 ( const T * a ) ...

Исходники находятся в файле median.h.

Наверх