Сортировка (часть 1)

Введение

Рассматриваемые здесь задачи можно отнести к наиболее часто встречающимся классам комбинаторных задач. Почти во всех машинных приложениях множество объектов должно быть переразмещено в соответствии с некоторым заранее определенным порядком. Например, при обработке коммерческих данных часто бывает необходимо расположить их по алфавиту или по возрастанию номеров. В числовых расчетах иногда требуется знать наибольший корень многочлена, и т.д.

Будем считать заданной таблицу с $$n$$ именами, обозначаемыми $$x_1$$, $$x_2,\ldots,x_n$$. Каждое имя $$x_i$$ принимает значение из пространства имен, на котором определен линейный порядок. Будем считать, что никакие два имени не имеют одинаковых значений; то есть любые $$x_i^{},x_j$$ обладают тем свойством, что если $$i \ne j$$, то либо $$x_i < x_j$$, либо $$x_i > x_j$$. Ограничение $$x_i \ne x_j$$ при $$i \ne j$$ упрощает анализ без потери общности, ибо и при наличии равных имен корректность идей и алгоритмов не нарушается. Наша цель состоит в том, чтобы выяснить что- нибудь относительно перестановки $$\Pi=(\pi_1,\pi_2,\ldots,\pi_n)$$ для которой $$x_{\pi _1 } < x_{\pi _2 } < \ldots < x_{\pi _n }$$. В задаче полной сортировки требуется полностью определить $$\Pi$$, хотя обычно это делается неявно путем переразмещения имени в порядке возрастания. В задачах частичной сортировки требуется либо извлечь частичную информацию о $$\Pi$$ (например, $$\Pi_i$$ для нескольких значений $$i$$ ), либо полностью определить $$\Pi$$ по некоторой заданной частичной информации о ней (так обстоит дело при слиянии двух упорядоченных таблиц).

При внутренней сортировке решается задача полной сортировки для случая достаточно малой таблицы, умещающейся непосредственно в адресной памяти. Внешняя сортировка представляет собой задачу полной сортировки для случая такой большой таблицы, что доступ к ней организован по частям, расположенным на внешних запоминающих устройствах. Частичная сортировка - задачи выбора $$i$$ - наибольшего имени и слияния двух упорядоченных таблиц.

Внутренняя сортировка

Существует по крайней мере пять широких классов алгоритмов внутренней сортировки.

Эти классы нельзя назвать ни взаимоисключающими, ни исчерпывающими: одни алгоритмы сортировки можно с полным основанием отнести более чем к одному классу (пузырьковую сортировку можно рассматривать и как выбор, и как обмен), а другие не укладываются ни в один из классов. Тем не менее, перечисленные пять классов достаточно удобны для классификации обсуждаемых алгоритмов сортировки.

Сосредоточим внимание на первых четырех классах алгоритмов сортировки. Алгоритмы, основанные на слиянии, приемлемы для внутренней сортировки, но более естественно рассматривать их как методы внешней сортировки.

В описываемых алгоритмах сортировки имена образуют последовательность, которую будем обозначать $$x_1,x_2,\ldots,x_n$$ независимо от возможных пересылок данных; таким образом, значением $$x_i$$ является любое текущее имя в $$i$$ -й позиции последовательности. Многие алгоритмы сортировки наиболее применимы к массивам; в этом случае $$x_i$$ обозначает $$i$$ -й элемент массива. Другие алгоритмы более приспособлены для работы со связанными списками: здесь $$x_i$$ обозначает $$i$$ -й элемент списка. Следующие обозначения используются для пересылок данных:

$$x_i \leftrightarrow x_j$$ значения $$x_i$$ и $$x_j$$ меняются местами. $$x_i \leftarrow y$$ значение $$y$$ присваивается имени $$x_i$$. $$y \leftarrow x_j$$ значение имени $$x_j$$ присваивается $$y$$.

Таким образом, операция $$x_i \leftarrow x_j$$, которая встречается в различных алгоритмах сортировки, временно нарушает предположение о том, что никакие два имени не имеют одинаковых значений. Однако это условие всегда обязательно восстанавливается.

В каждом из рассматриваемых алгоритмов будем считать, что имена нужно сортировать на месте. Другими словами, переразмещение имен должно происходить внутри последовательности $$x_1,x_2,\ldots,x_n$$ ; при этом существуют одна или две дополнительные ячейки, в которых временно размещается значение имени. Ограничение "на месте" основано на предположении, будто число имен настолько велико, что во время сортировки не допускается перенос их в другую область памяти. Если в распоряжении имеется память, достаточная для такого переноса, то некоторые из обсуждаемых алгоритмов можно значительно ускорить. Эти рассмотрения заставляют нас в алгоритмах распределяющей сортировки и сортировки слиянием реализовать последовательность $$x_1,x_2,\ldots,x_n$$ как связанный список.

Вставка

Вставка - простейшая сортировка вставками проходит через этапы $$j = 2,3,\ldots,n$$: на этапе $$j$$ имя $$x_j$$ вставляется на свое правильное место среди $$x_1,x_2,\ldots,x_{j - 1}$$.

При вставке имя $$x_j$$ временно размещается в $$X$$, и просматриваются имена $$x_{j - 1},x_{j - 2},\ldots,x_i$$ ; они сравниваются с $$X$$ и сдвигаются вправо, если обнаруживается, что они больше $$X$$. Имеется фиктивное имя $$x_0$$, значение которого $$- \infty$$ служит для остановки просмотра слева. На рис. 14.1 работа этого алгоритма проиллюстрирована на примере таблицы из пяти имен.

Эффективность этого алгоритма, как и большинства алгоритмов сортировки, зависит от числа сравнений имен и числа пересылок данных, осуществляемых в трех случаях : худшем, среднем (в предположении, что все $$n$$! перестановок равновероятны) и лучшем.

Обменная сортировка

Обменная сортировка некоторым систематическим образом меняет местами пары имен, не отвечающие порядку, до тех пор, пока такие пары существуют. Фактически алгоритм 14.1 можно рассматривать как обменную сортировку, в которой имя $$x_j$$ меняется местами со своим соседом слева, пока не оказывается на правильном месте. В этом разделе мы обсуждаем два типа обменных сортировок: хорошо известную, но относительно неэффективную пузырьковую сортировку и быструю сортировку — один из лучших со всех точек зрения алгоритмов внутренней сортировки.

Пузырьковая сортировка. Наиболее очевидный метод систематического обмена местами имен с неправильным порядком состоит в просмотре пар смежных имен последовательно слева направо и перемене мест тех имен, которые не отвечают порядку.

Эта техника получила название пузырьковой сортировки, так как большие имена "пузырьками всплывают" вверх (то есть на правый конец) таблицы. В алгоритме 14.2 эта простая идея реализуется с одним небольшим усовершенствованием: ясно, что не имеет смысла продолжать просмотр для больших имен (в правом конце таблицы), про которые известно, что они находятся на своих окончательных позициях. В алгоритме 14.2 используется переменная $$b$$, значение которой в начале цикла $$while$$ равно наибольшему индексу $$t$$, такому, что про имя $$x_t$$ еще не известно, стоит ли оно в окончательной позиции. На рис. 14.2 показана работа алгоритма на примере таблицы с $$n = 8$$ именами.

Анализ пузырьковой сортировки зависит от трех факторов: числа проходов (то есть числа выполнений тела цикла $$while$$ ), числа сравнений $$x_j > x_{j + 1}$$ и числа обменов $$x_j \leftrightarrow x_{j + 1}$$. Число обменов равно, как в алгоритме 14.1, числу инверсий: 0 в лучшем случае, $$\frac{1} {2}n(n - 1)$$ в худшем случае и $$\frac{1} {4}n(n - 1)$$ - в среднем. Рисунок 14.2 дает возможность предположить, что каждый проход пузырьковой сортировки, исключая последний, уменьшает на единицу каждый ненулевой элемент вектора инверсий и циклически сдвигает вектор на одну позицию влево; легко доказать, что это верно в общем случае, и поэтому число проходов равно единице плюс наибольший элемент вектора инверсий. В лучшем случае имеется всего один проход, в худшем случае - $$n$$ проходов и в среднем - $$\sum {kP_k }$$ проходов, где $$P_k$$ - вероятность того, что наибольшим элементом вектора инверсии является $$k - 1$$. Общее число сравнений имен трудно определить, но можно показать, что оно равно $$n - 1$$ в лучшем случае, $$\frac{1} {2}n(n - 1)$$ в худшем случае и $$\frac{1} {2}(n^2 - n\ln n) +$$ $${\rm O}(n)$$ - в среднем.

Пузырьковую сортировку можно несколько улучшить, но при этом она все еще не сможет конкурировать с более эффективными алгоритмами сортировки. Ее единственным преимуществом является простота.

Как в простой сортировке вставками, так и в пузырьковой сортировке (алгоритм 14.2) основной причиной неэффективности является тот факт, что обмены дают слишком малый эффект, так как в каждый момент времени имена сдвигаются только на одну позицию. Такие алгоритмы непременно требуют порядка $$n^2$$ операций, как в среднем, так и в худшем случаях.

Быстрая сортировка. Идея метода быстрой сортировки состоит в том, чтобы выбрать одно из имен в таблице и использовать его для разделения таблицы на две подтаблицы, составленные соответственно из имен меньших и больших выбранного, которые затем рекурсивно сортируются с использованием быстрой сортировки. Разделение можно реализовать, одновременно просматривая таблицу и слева направо, и справа налево, меняя местами имена в неправильных частях таблицы. Имя, используемое для расщепления таблицы, затем помещается между двумя подтаблицами, и две подтаблицы сортируются рекурсивно.

В алгоритме 14.3 показаны детали быстрой сортировки для сортировки таблицы $$(x_f,x_{f + 1},\ldots,x_l )$$, где $$x_j$$ используется для разбиения таблицы на подтаблицы. На рис. 14.3 показано, как алгоритм 14.3 использует два указателя $$i$$ и $$j$$ для просмотра таблицы во время разбиения. В начале цикла " $$while$$ $$i < j$$ " $$i$$ и $$j$$ указывают соответственно на первое и последнее имена, о которых известно, что они находятся не в тех частях файла, в которых требуется. Когда $$i < j$$ встречаются, то есть когда $$i \geqslant j$$, все имена находятся в соответствующих частях таблицы и $$x_f$$ помещается между двумя частями, меняясь при этом местами с $$x_j$$, алгоритм предполагает, что имя $$x_{i + 1}$$ определено и больше, чем $$x_f,x_{f + 1},\ldots,x_l$$.

Алгоритм 14.3 изящен, но непрактичен. Проблема состоит в том, что рекурсия используется для записи подтаблиц, которые рассматриваются на более поздних этапах, и в худших случаях (когда таблица уже отсортирована) глубина рекурсии может равняться $$n$$. Следовательно, для стека, реализующего рекурсию, необходима память, пропорциональная $$n$$ ; для больших $$n$$ такое требование становится неприемлемым. Кроме того, второе рекурсивное обращение к быстрой сортировке в алгоритме 14.3 может быть легко исключено. По этим причинам мы предлагаем алгоритм 14.4, итерационный вариант быстрой сортировки, в которой стек ведется явно. Элементом стека является пара $$(f,l)$$: когда пара находится в стеке, это значит, что нужно сортировать соответствующие $$x_f,\ldots,x_l$$. Алгоритм 14.4 помещает в стеке большую из двух подтаблиц и немедленно применяет алгоритм к меньшей подтаблице. Это уменьшает глубину стека в худшем случае примерно до $$\lg n$$. Заметим, что подтаблицы длины 1 игнорируются и что расщепление подтаблицы делается с использованием случайно выбранного имени в этой подтаблице.