Алгоритм поиска медианы семи чисел:
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.
Наверх
|