Нижние оценки для числа
сравнений при сортировке

Нижние оценки для числа сравнений

Пусть имеется n различных по весу камней и весы, которые позволяют за одно взвешивание определить, какой из двух выбранных нами камней тяжелее. (В программистских терминах: мы имеем доступ к функции тяжелее(i,j:1..n):boolean.) Надо упорядочить камни по весу, сделав как можно меньше взвешиваний (вызовов функции тяжелее).  Разумеется, число взвешиваний зависит не только от выбранного нами алгоритма, но и от того, как оказались расположены камни. Сложностью алгоритма назовем число взвешиваний при наихудшем расположении камней. 


$\scriptstyle{\blacktriangleright}$ 4.4.1. Доказать, что сложность любого алгоритма сортировки n камней не меньше $\log_2 n!$. (Здесь $n!=1\cdot2\cdots n$.)

Решение. Пусть имеется алгоритм сложности не более d . Для каждого из n! возможных расположений камней запротоколируем результаты взвешиваний (обращений к функции тяжелее); их можно записать в виде последовательности из не более чем d нулей и единиц. Для единообразия дополним последовательность нулями, чтобы ее длина стала равной d . Тем самым у нас имеется n! последовательностей из d нулей и единиц. Все эти последовательности разные -- иначе наш алгоритм дал бы одинаковые ответы для разных порядков (и один из ответов был бы неправильным). Получаем, что $2^d \geqslant n!$ -- что и требовалось доказать.

Другой способ объяснить то же самое -- рассмотреть дерево вариантов, возникающее в ходе выполнения алгоритма, и сослаться на то, что дерево высоты d не может иметь более 2d листьев.$\scriptstyle\blacktriangleleft$

Это рассуждение показывает, что любой алгоритм сортировки, использующий только сравнения элементов массива и их перестановки, требует не менее $Cn\log n$ действий, так что наши алгоритмы близки к оптимальным. Однако алгоритм сортировки, использующий другие операции, может действовать быстрее. Вот один из примеров.


$\scriptstyle{\blacktriangleright}$ 4.4.2. Имеется массив целых чисел ${\hbox{\tt a[1]}}\ldots{\hbox{\tt a[n]}}$, причем все числа неотрицательны и не превосходят m. Отсортировать этот массив; число действий порядка ${\hbox{\tt m}}+{\hbox{\tt n}}$.

Решение. Для каждого числа от 0 до m подсчитываем, сколько раз оно встречается в массиве. После этого исходный массив можно стереть и заполнить заново в порядке возрастания, используя сведения о кратности каждого числа.$\scriptstyle\blacktriangleleft$

Отметим, что этот алгоритм не переставляет числа в массиве, как большинство других, а << записывает их туда заново>>.

Есть также метод сортировки, в котором последовательно проводится ряд << частичных сортировок>> по отдельным битам. Начнем с такой задачи:


$\scriptstyle{\blacktriangleright}$ 4.4.3. В массиве ${\hbox{\tt a[1]}}\ldots{\hbox{\tt a[n]}}$ целых чисел переставить элементы так, чтобы четные числа шли перед нечетными (не меняя взаимный порядок в каждой из групп).

Решение. Сначала спишем (во вспомогательный массив) все четные, а потом -- все нечетные.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 4.4.4. Имеется массив из n чисел от до 2k-1 , каждое из которых мы будем рассматривать как k -битовое слово из нулей и единиц. Используя проверки <<i -ый бит равен >> и <<i -ый бит равен 1 >> вместо сравнений, отсортировать все числа за время порядка nk .

 

Решение. Отсортируем числа по последнему биту (см. предыдущую задачу), затем по предпоследнему и так далее. В результате они будут отсортированы. В самом деле, индукцией по i легко доказать, что после i шагов любые два числа, отличающиеся только в i последних битах, идут в правильном порядке. (Вариант: после i шагов i -битовые концы чисел идут в правильном порядке.)$\scriptstyle\blacktriangleleft$

Аналогичный алгоритм может быть применен для m -ичной системы счисления вместо двоичной. При этом полезна такая вспомогательная задача:


$\scriptstyle{\blacktriangleright}$ 4.4.5. Даны n чисел и функция f , принимающая (на них) значения $1\ldots m$. Требуется переставить числа в таком порядке, чтобы значения функции f не убывали (сохраняя порядок для чисел с равными значениями f ). Число действий порядка m+n .

[Указание. Завести m списков суммарной длины n (как это сделать, смотри в главе 6 о типах данных) и помещать в i -ый список числа, для которых значение функции f равно i . Вариант: посчитать для всех i , сколько имеется чисел x с f(x)=i , после чего легко определить, с какого места нужно начинать размещать числа x с f(x)=i .]$\blacktriangleleft$


pvv
1/8/1999