Пусть имеется n различных по весу камней и весы, которые позволяют за одно взвешивание определить, какой из двух выбранных нами камней тяжелее. (В программистских терминах: мы имеем доступ к функции тяжелее(i,j:1..n):boolean.) Надо упорядочить камни по весу, сделав как можно меньше взвешиваний (вызовов функции тяжелее). Разумеется, число взвешиваний зависит не только от выбранного нами алгоритма, но и от того, как оказались расположены камни. Сложностью алгоритма назовем число взвешиваний при наихудшем расположении камней.
4.4.1. Доказать, что сложность любого алгоритма сортировки n
камней не меньше . (Здесь
.)
Другой способ объяснить то же самое -- рассмотреть дерево вариантов, возникающее в ходе выполнения алгоритма, и сослаться на то, что дерево высоты d не может иметь более 2d листьев.
Это рассуждение показывает, что любой алгоритм сортировки, использующий только сравнения элементов массива и их перестановки, требует не менее действий, так что наши алгоритмы близки к оптимальным. Однако алгоритм сортировки, использующий другие операции, может действовать быстрее. Вот один из примеров.
4.4.2. Имеется массив целых чисел , причем
все числа неотрицательны и не превосходят m. Отсортировать этот
массив; число действий порядка .
Отметим, что этот алгоритм не переставляет числа в массиве, как большинство других, а << записывает их туда заново>>.
Есть также метод сортировки, в котором последовательно проводится ряд << частичных сортировок>> по отдельным битам. Начнем с такой задачи:
4.4.3. В массиве целых чисел переставить
элементы так, чтобы четные числа шли перед нечетными (не меняя
взаимный порядок в каждой из групп).
4.4.4. Имеется массив из n чисел от до 2k-1 ,
каждое из которых мы будем рассматривать как k -битовое слово из нулей и
единиц.
Используя проверки <<i -ый бит равен >> и
<<i -ый бит
равен 1 >> вместо сравнений, отсортировать все числа за время
порядка nk .
Аналогичный алгоритм может быть применен для m -ичной системы счисления вместо двоичной. При этом полезна такая вспомогательная задача:
4.4.5. Даны n чисел и функция f , принимающая
(на них) значения . Требуется переставить числа в
таком порядке, чтобы значения функции f не убывали (сохраняя
порядок для чисел с равными значениями f ).
Число действий порядка
m+n .