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

Выбор

В сортировке посредством выбора основная идея состоит в том, чтобы идти по шагам $$i = 1,2,\ldots,n$$, находя $$i$$ -е наибольшее (наименьшее) имя и помещая его на его место на $$i$$ -ом шаге. Простейшая форма сортировки выбором представлена алгоритмом 15.1: $$i$$ -е наибольшее имя находится очевидным способом просмотром оставшихся $$n - i + 1$$ имен. Число сравнений имен на $$i$$ -ом шаге равно $$n - i$$, что приводит к общему числу сравнений имен $$(n - 1) + (n - 2) + \ldots + 1 = \frac{1} {2}n(n - 1)$$ независимо от входа, поэтому ясно, что это не очень хороший способ сортировки.

Несмотря на неэффективность алгоритма 15.1, идея выбора может привести и к эффективному алгоритму сортировки. Весь вопрос в том, чтобы найти более эффективный метод определения $$i$$ -го наибольшего имени, чего можно добиться, используя механизм турнира с выбыванием. Суть его такова: сравниваются $$x_1 :x_2,x_3 :x_4,x_5 :x_6,\ldots,x_{n - 1} :x_n$$, затем сравниваются "победители" (то есть большие имена) этих сравнений и т.д.; эта процедура для $$n = 16$$ показана на рис. 15.1. Заметим, что для определения наибольшего имени этот процесс требует $$n - 1$$ сравнений имен; но, определив наибольшее имя, мы обладаем большим объемом информации о втором по величине (в порядке убывания) имени: оно должно быть одним из тех, которые "потерпели поражение" от наибольшего имени. Таким образом, второе по величине имя теперь можно определить, заменяя наибольшее имя на $$- \infty$$ и вновь осуществляя сравнение вдоль пути от наибольшего имени к корню. На рис. 15.2 эта процедура показана для дерева из рис. 15.1.

Идея турнира с выбыванием прослеживается при сортировке весьма отчетливо, если имена образуют пирамиду. Пирамида - это полностью сбалансированное бинарное дерево высоты $$h$$, в котором все листья находятся на расстоянии $$h$$ или $$h - 1$$ от корня и все потомки узла меньше его самого; кроме того, в нем все листья уровня максимально смещены влево. На рис. 15.3 показано множество имен, организованных в виде пирамиды. Чтобы получить удобное линейное представление дерева, пирамиду можно хранить по уровням в одномерном массиве: сыновья имени из $$i$$ -ой позиции есть имена в позициях $$2i$$ и $$2i + 1$$. Таким образом, пирамида, представленная на рисунке 15.3, принимает вид

Заметим, что в пирамиде наибольшее имя должно находиться в корне и, таким образом, всегда в первой позиции массива, представляющего пирамиду. Обмен местами первого имени с $$n$$ -м помещает наибольшее имя в его правильную позицию, но нарушает свойство пирамидальности в первых $$n - 1$$ именах. Если мы можем сначала построить пирамиду, а затем эффективно восстановить ее, то все в порядке, так как тогда можно производить сортировку следующим образом: построить пирамиду из $$x_1,x_2,\ldots,x_n$$,

Это общее описание пирамидальной сортировки.

Процедура RESTORE $$(j,k)$$ восстановления пирамиды из последовательности $$x_j,x_{j + 1},\ldots,x_k$$ в предположении, что все поддеревья суть пирамиды, такова:

Переписывая это итеративным способом и дополняя деталями, мы получим алгоритм 15.2.

Распределяющая сортировка

Обсуждаемый здесь алгоритм сортировки отличается от рассматривавшихся до сих пор тем, что он основан не на сравнениях между именами, а на представлении имен. Мы полагаем, что каждое из имен $$x_1,x_2,\ldots,x_n$$ имеет вид$$x_i = (x_{i,p},x_{i,p - 1},\ldots,x_{i,1} )$$ и их нужно отсортировать в возрастающем лексикографическом порядке, то есть$$x_i = (x_{i,p},x_{i,p - 1},\ldots,x_{i,1} ) < (x_{j,p}^,,x_{j,p - 1},\ldots,x_{j,1} ) = x_j$$ тогда и только тогда, если для некоторого $$t \leqslant p$$ имеем $$x_{i,l} = x_{j,l}$$ для $$l > t$$ и $$x_{i,t} < x_{j,t}$$. Для простоты будем считать, что $$0 \leqslant x_{i,l} < r$$, и поэтому имена можно рассматривать как целые, представленные по основанию $$r$$, так что каждое имя имеет $$p$$ $$r$$ -ичных цифр. Более короткие имена дополняются нулями.

Цифровая распределяющая сортировка

Цифровая распределяющая сортировка основана на наблюдении, что если имена уже отсортированы по младшим разрядами $$l,l - 1,\ldots,1$$, то их можно полностью отсортировать, сортируя только по старшим разрядам $$p,p - 1,\ldots,i + 1$$ при условии, что сортировка осуществляется таким образом, чтобы не нарушить относительный порядок имен с одинаковыми цифрами в старших разрядах. Заметим, что к самой таблице обращаются по правилу "первым включается – первым исключается", и поэтому лучшим способом представления являются очереди. В частности, предположим, что с каждым ключом $$x_i$$ ассоциируется поле связи $$LINK_i$$ ; тогда эти поля связи можно использовать для сцепления всех имен в таблице вместе во входную очередь $$Q$$. При помощи полей связи можно также сцеплять имена в очереди $$Q_0,Q_1,\ldots,Q_{r - 1}$$, используемые для представления стопок. После того как имена распределены по стопкам, очереди, представляющие эти стопки, связываются вместе для получения вновь таблицы $$Q$$. Алгоритм 15.4. представляет эту процедуру в общих чертах (очереди описаны в лекции 11). В результате применения алгоритма очередь $$Q$$ будет содержать имена в порядке возрастания; то есть имена будут связаны в порядке возрастания полями связи, начиная с головы очереди $$Q$$.

Использовать поля связи $$LINK_1,\ldots LINK_n$$ для формирования $$x_1,\ldots,x_n$$ во входную очередь $$Q$$

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

В методах сортировки, обсуждавшихся в предыдущем разделе, мы полагали, что таблица умещается в быстродействующей внутренней памяти. Хотя для большинства реальных задач обработки данных это предположение слишком сильно, оно, как правило, выполняется для комбинаторных алгоритмов. Сортировка обычно используется только для некоторого сокращения времени работы алгоритмов, в которых сортировка применяется только для некоторого сокращения времени работы алгоритмов, когда оно недопустимо велико даже для задач "умеренных" размеров. Например, часто бывает необходимо сортировать отдельные предметы во времени исчерпывающего поиска (лекция 13), но поскольку такой поиск обычно требует экспоненциального времени, маловероятно, что подлежащая сортировке таблица будет настолько большой, чтобы потребовалось использование запоминающих устройств. Однако задача сортировки таблицы, которая слишком велика для основной памяти, служит хорошей иллюстрацией работы с данными большого объема, и поэтому в этом разделе мы обсудим важные идеи внешней сортировки. Более того, будем рассматривать только сортировку таблицы путем использования вспомогательной памяти с последовательным доступом. Условимся называть эту память лентой.

Общей стратегией в такой внешней сортировке является использование внутренней памяти для сортировки имен из ленты по частям так, чтобы производить исходные отрезки (известные также как цепочки ) имен в возрастающем порядке. По мере порождения эти отрезки распределяются по $$t$$ рабочим лентам, и затем производится их слияние по $$t$$ отрезков обратно на исходную $$(t + 1)$$ -ю ленту так, что она будет содержать меньшее число более длинных отрезков. Затем отрезки снова распределяются по остальным $$t$$ лентам, и снова производится их слияние по $$t$$ штук обратно на $$(t + 1)$$ -ю ленту. Процесс продолжается до тех пор, пока не получится один отрезок, то есть пока таблица не будет полностью отсортирована. Имеются, таким образом, две отдельные проблемы: как порождать исходные отрезки и как осуществлять слияние.

Самый очевидный метод для получения исходных отрезков состоит в том, что можно просто считывать $$(t + 1)$$ -ю ленту $$m$$ имен, рассортировывать их во внутренней памяти и записывать их на ленту в виде отрезка, продолжая процесс до тех пор, пока не будут исчерпаны все имена. Все полученные таким образом исходные отрезки содержат $$m$$ имен (исключая, возможно, последний отрезок). Поскольку число исходных отрезков в конце концов определяет время слияния, мы хотели бы найти некоторый метод образования более длинных исходных отрезков и, следовательно, меньшего их количества. Это можно сделать, используя для сортировки идею турнира (пирамидальную сортировку). При этом подходе $$m$$ имен, которые умещаются в памяти, хранятся в виде такой пирамиды, что сыновья узла больше узла (вместо того, чтобы быть меньше его). Этот метод отвечает определению "победителя" при сравнении имен в сортировках типа турнира как меньшего из двух имен, и это позволяет нам следить за наименьшим именем.

Порождение исходных отрезков продолжается следующим образом. Из входной ленты считываются первые $$m$$ имен, и затем из них формируется пирамида, как описано выше. Наименьшее имя выводится как первое в первом отрезке и заменяется в пирамиде следующим именем из входной ленты в соответствии с алгоритмом 15.2. модифицированным так, чтобы для восстановления пирамиды следить за наименьшим, а не за наибольшим именем. Процесс, известный как выбор с замещением, продолжается таким образом, что к текущему отрезку всегда добавляется наименьшее в пирамиде имя, большее или равное имени, которое последним добавлено к отрезку; при этом добавленное имя заменяется на следующее из входной ленты и восстанавливается пирамида. Когда в пирамиде нет имен, больших, чем последнее имя в текущем отрезке, отрезок обрывается и начинается новый. Этот процесс продолжается до тех пор, пока все имена не сформируются в отрезки.

Разумный путь реализации этой процедуры состоит в том, чтобы рассматривать каждое имя $$x$$ как пару $$(r,x)$$, где $$r$$ есть номер отрезка, в котором находится $$x$$. Иначе говоря, считается, что пирамида состоит из пар $$(r_1,x_1 ),(r_2,x_2 ),\ldots,(r_m,x_m )$$ ; сравнения между парами осуществляются лексикографически. Когда считывается имя, меньшее последнего имени в текущем отрезке, оно должно быть в следующем отрезке, и благодаря наличию номера отрезка это имя будет ниже всех имен пирамиды, которые входят в текущий отрезок.

Порождает ли этот выбор с замещением длинные отрезки? Ясно, что он делает это, по крайней мере, не хуже, чем очевидный метод, так как все отрезки (кроме, возможно, последнего) содержат не меньше $$m$$ имен. На самом деле можно показать, что средняя длина отрезков, порождаемых выбором с замещением, равна $$2m$$, и это вполне можно считать улучшением по сравнению с очевидным методом, в котором средняя длина отрезков равна $$m$$. Конечно, в лучшем случае все заканчивается только одним исходным отрезком, то есть отсортированной таблицей.

После того, как порождены исходные отрезки, возникает задача повторного распределения их по рабочим лентам и слияния их вместе до тех пор, пока в конце концов мы не получим окончательную отсортированную таблицу. Простейший метод состоит в том, чтобы распределить отрезки по лентам $$1,2,\ldots,t$$ равномерно и произвести их слияние на ленту $$t + 1$$. Получаемые в результате отрезки снова равномерно распределить по лентам $$1,2,\ldots,t$$ и снова произвести слияние, образуя более длинные отрезки на ленте $$t + 1$$. Процесс продолжается до тех пор, пока на ленте $$t + 1$$ не останется только один отрезок (отсортированная таблица).

Частичная сортировка

Ранее мы изучали проблему полного упорядочения множества имен, не имея a priori информации об абстрактном порядке имен. Имеется два очевидных уточнения этой проблемы. Вместо полного упорядочения требуется только определить $$k$$ -е наибольшее имя (то есть $$k$$ -е имя в порядке убывания) (выбор) или, вместо того чтобы начинать процесс, не располагая информацией о порядке, начинать с двух отсортированных подтаблиц (слияние). Мы рассматриваем обе проблемы частичной сортировки.

Частичная сортировка (выбор)

Как при данных именах $$x_1,x_2,\ldots,x_n$$ можно найти $$k$$ -е из наибольших в порядке убывания? Задача, очевидно, симметрична: отыскание $$(n - k + 1)$$ -го наибольшего ( $$k$$ -го наименьшего) имени можно осуществить, используя алгоритм отыскания $$k$$ -го наибольшего, но меняя местами действия, предпринимаемые при результатах < и >сравнения имен. Таким образом, отыскание наибольшего имени $$(k = 1)$$ эквивалентно отысканию наименьшего имени $$(k = n)$$ ; отыскание второго наибольшего имени $$(k = 2)$$ эквивалентно отысканию второго наименьшего $$(k = n - 1)$$ и т.д.

Конечно, все перечисленные варианты задачи выбора можно решить, используя любой из методов полной сортировки имен и затем тривиально обращаясь к $$k$$ -му наибольшему. Такой подход потребует порядка $$n\log n$$ сравнений имен независимо от значений $$k$$.

При использовании алгоритма сортировки для выбора наиболее подходящим будет один из алгоритмов, основанных на выборе: либо простая сортировка выбором (алгоритм 15.1) либо пирамидальная сортировка (алгоритм 15.3). В каждом случае мы можем остановиться после того, как выполнены первые $$k$$ шагов. Для простой сортировки выбором это означает использование$$(n - 1) + (n - 2) + \ldots + (n - k) = kn - \frac{{k(k + 1)}}{2}$$ сравнений имен, а для пирамидальной — использование $$n + k\lg n$$ сравнений имен. В обоих случаях мы получаем больше информации, чем нужно, потому что мы полностью определяем порядок $$k$$ наибольших имен.

Частичная сортировка (слияние)

Вторым направлением исследования частичной сортировки является задача слияния двух отсортированных таблиц $$x_1 \leqslant x_2 \leqslant \ldots \leqslant x_n$$ и $$y_1 \leqslant y_2 \ldots \leqslant y_m$$ в одну отсортированную таблицу $$z_1 \leqslant z_2 \leqslant \ldots \leqslant z_{n + m}$$. Существует очевидный способ это сделать: таблицы, подлежащие слиянию, просматривать параллельно, выбирая на каждом шаге меньшее из двух имен и помещая его в окончательную таблицу. Этот процесс немного упрощается добавлением имен-сторожей $$x_{n + 1} = y_{m + 1} = \infty$$, как в алгоритме 15.5. В этом алгоритме $$i$$ и $$j$$ указывают, соответственно, на последние имена в двух входных таблицах, которые еще не были помещены в окончательную таблицу.