Медиана восьми чисел

Для чётного количества чисел медианой считается среднее арифметическое двух средних чисел.
Данный алгоритм в лучшем случае находит медиану за 11 сравнений, а в худшем - за 14.
Вот его краткое описание:
Вначале разделим числа на две четвёрки и упорядочим каждую из них по возрастанию. Пусть ( к примеру ) третий элемент первой четвёрки меньше третьего элемента второй. Тогда мы можем отбросить минимальный элемент первой четвёрки и два максимальных элемента второй четвёрки. Останутся упорядоченные тройка и двойка элементов. Сравниваем средний элемент тройки и максимум двойки и отбрасываем крайние числа аналогично тому, как это сделано в алгоритме для медианы шести чисел.
Если рассмотреть все 8! = 40320 перестановок 8 чисел, то получим следующую статистику:

		11 -  2304
		12 - 11392
		13 - 17920
		14 -  8704

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

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

template<class T> T _median8 ( const T * a )
{
    SemiRef<const T> a0(a[0]), a1(a[1]), a2(a[2]), a3(a[3]),
                     a4(a[4]), a5(a[5]), a6(a[6]), a7(a[7]);
// Упорядочивание первой четвёрки
    sort123 ( a0, a1, a2, a3 );
// Упорядочивание второй четвёрки
    sort123 ( a4, a5, a6, a7 );
// Отбрасывание крайних чисел и вычисление медианы
    if ( a2 < a6 )
    {
        if ( a2 < a5 )
            return ( _max ( a2, a4 ) + _min ( a3, a5 ) ) / 2;
        else
            return ( _max ( a1, a5 ) + a2 ) / 2;
    }
    else
    {
        if ( a1 < a6 )
            return ( _max ( a1, a5 ) + a6 ) / 2;
        else
            return ( _max ( a0, a6 ) + _min ( a1, a7 ) ) / 2;
    }
}
Описание шаблона классов SemiRef находится здесь.

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

Наверх