Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией
 Скачать 2.67 Mb.
|
|
Глава 2 Сортировка 2.1. Введение ............................ 70 2.2. Сортировка массивов ........ 72 2.3. Эффективные методы сортировки ................................ 81 2.4. Сортировка последовательностей ................ 97 Упражнения ............................. 128 Литература .............................. 130 Сортировка 70 2.1. Введение Главная цель этой главы – дать богатый набор примеров, иллюстрирующих ис% пользование структур данных, введенных в предыдущей главе, а также показать, что выбор структуры обрабатываемых данных оказывает глубокое влияние на ал% горитмы решения задачи. Тема сортировки хороша еще и тем, что показывает, как одна и та же задача может решаться с помощью многих разных алгоритмов, при% чем у каждого из них есть преимущества и недостатки, которые следует взвесить в условиях конкретной задачи. Под сортировкой обычно понимают процесс перестановки объектов некоторого множества в определенном порядке. Цель сортировки – облегчить в дальнейшем поиск элементов отсортированного множества. Это очень часто выполняемая, фун% даментальная операция. Объекты сортируются в телефонных справочниках, в списках налогоплательщиков, в оглавлениях книг, в библиотеках, в словарях, на складах, то есть почти всюду, где нужно искать хранимые объекты. Даже детей учат приводить вещи «в порядок», и они сталкиваются с некоторыми видами сортировки задолго до того, как начнут изучать арифметику. Поэтому сортировка – весьма важная операция, особенно в обработке данных. Кажется, ничто не поддается сортировке лучше, чем данные! И все же при изуче% нии сортировки наибольший интерес для нас будут представлять еще более фундаментальные приемы, используемые при построении алгоритмов. Нелегко найти приемы, которые не использовались бы так или иначе в связи с алгоритма% ми сортировки. При этом сортировка – идеальная тема для демонстрации широ% кого разнообразия алгоритмов, решающих одну и ту же задачу, причем многие из них в каком%нибудь смысле оптимальны, и почти каждый из них имеет какие%ни% будь преимущества перед остальными. Поэтому здесь хорошо видно, зачем нужен анализ эффективности алгоритмов. Более того, на примере сортировок становит% ся понятно, что можно получить весьма существенный выигрыш в эффектив% ности, разрабатывая хитроумные алгоритмы, даже если уже имеются очевидные методы. Влияние структуры обрабатываемых данных на выбор алгоритма – само по себе обычное явление – в случае сортировок проявляется настолько сильно, что методы сортировки обычно делят на два типа, а именно сортировки массивов и сортировки (последовательных) файлов. Эти два типа часто называют внутрен ней и внешней сортировками, так как массивы хранятся в быстрой, допускающей произвольный доступ внутренней оперативной памяти, а файлы уместны при ра% боте с медленными, но вместительными внешними устройствами хранения (дис% ками и лентами). Важность такого деления очевидна из примера сортировки пронумерованных карточек. Представление карточек массивом соответствует раскладыванию их перед сортировщиком так, чтобы каждая карточка была непос% редственно видна и доступна (см. рис. 2.1). Однако при файловой организации карточек в каждой стопке видна только верхняя карточка (см. рис. 2.2). 71 Очевидно, что такое ограничение будет иметь серьезные последствия для ме% тода сортировки, но оно неизбежно, если карточек так много, что они не умещают% ся на столе все сразу. Сначала введем некоторые термины и обозначения, которые будут использо% ваться на протяжении этой главы. Если даны n элементов a 0 , a 1 , ... , a n–1 то сортировка состоит в их перестановке к виду a k0 , a k1 , ... , a k[n–1] таким образом, чтобы для некоторой упорядочивающей функции f f(a k0 ) ≤ f(a k1 ) ≤ ... ≤ f(a k[n–1] ) Рис. 2.1. Сортировка массива Рис. 2.2. Сортировка файла Введение Сортировка 72 Часто значение такой упорядочивающей функции не вычисляется, а хранится как явная компонента (поле) в каждом элементе. Это значение называется клю чом элемента. Следовательно, записи особенно хорошо подходят для представле% ния элементов и могут быть объявлены, например, следующим образом: TYPE Item = RECORD key: INTEGER; (* # *) END Другие компоненты представляют данные, нужные для иных целей, а ключ используется просто для идентификации элементов. Однако для алгоритмов сортировки важен только ключ. Поэтому в дальнейшем мы будем игнорировать любую дополнительную информацию и примем, что тип Item определен как INTEGER . Такой выбор типа ключа несколько произволен. Очевидно, с равным ус% пехом можно использовать любой тип, для которого определено отношение пол% ного порядка. Метод сортировки называют устойчивым, если он сохраняет относительный порядок элементов с равными ключами. Устойчивость сортировки часто жела% тельна, если элементы уже упорядочены (отсортированы) по некоторым вторич% ным ключам, то есть свойствам, не отраженным в основном ключе. Данная глава не является всеобъемлющим обзором методов сортировки. Мы предпочитаем уделить больше внимания некоторым избранным алгоритмам. Ин% тересующийся читатель найдет тщательный разбор сортировок в великолепном и полном обзоре Кнута [2.7] (см. также Лорин [2.8]). 2.2. Сортировка массивов Главное требование при разработке алгоритмов сортировки массивов – эконом% ное использование доступной оперативной памяти. Это означает, что пере% становки, с помощью которых упорядочиваются элементы, должны выполняться in situ (лат.: на месте – прим. перев.), то есть не требуя дополнительной временной памяти, так что методы, которые требуют копирования элементов из массива a в массив%результат b , не представляют интереса. Ограничив таким образом выбор методов, попробуем классифицировать их в соответствии с эффективностью, то есть временем работы. Хорошая мера эффективности – число необходимых срав% нений ключей C , а также число перестановок элементов M . Эти величины являют% ся функциями числа сортируемых элементов n . Хотя хорошие алгоритмы сорти% ровки требуют порядка n*log(n) сравнений, мы сначала рассмотрим несколько простых и очевидных методов, которые называются простыми и требуют порядка n 2 сравнений ключей. Есть три важные причины, почему нужно рассмотреть про% стые методы, прежде чем переходить к быстрым алгоритмам: 1. Простые методы особенно хороши для обсуждения основных принципов сортировки. 2. Соответствующие программы легко понять. К тому же они короткие: ведь нужно помнить, что программы тоже занимают место в памяти! 73 3. Хотя более изощренные методы требуют меньшего числа операций, но эти операции обычно сложнее устроены; поэтому простые методы оказываются быстрее для малых n , хотя их нельзя использовать для больших n Алгоритмы сортировки, упорядочивающие элементы in situ, могут быть разде% лены на три основные категории в соответствии с используемым приемом: • сортировка вставками; • сортировка выбором; • сортировка обменом. Изучим и сравним эти три подхода. Алгоритмы будут работать с глобальной переменной a , чьи компоненты нужно отсортировать in situ. Компонентами являют% ся сами ключи. Для простоты мы игнорируем прочие данные, хранящиеся в записях типа Item. Во всех алгоритмах, которые будут разработаны в этой главе, предпо% лагается наличие массива a и константы n , равной числу элементов массива a : TYPE Item = INTEGER; VAR a: ARRAY n OF Item 2.2.1. Простая сортировка вставками Этот метод часто используется игроками в карты. Элементы (карты) мысленно разделяются на последовательность%приемник a 0 ... a i–1 и последовательность% источник a i ... a n–1 . На каждом шаге, начиная с i = 1 и затем увеличивая i на едини% цу, в последовательности%источнике берется i %й элемент и ставится в правильную позицию в последовательности%приемнике. В табл. 2.1 работа сортировки встав% ками показана на примере восьми взятых наугад чисел. Алгоритм простых вставок имеет вид FOR i := 1 TO n–1 DO x := a[i]; x a 0 ... a i–1 END Таблица 2.1. Таблица 2.1. Таблица 2.1. Таблица 2.1. Таблица 2.1. Пример работы простой сортировки вставками Начальные ключи: 44 55 55 55 55 55 12 42 94 18 06 67 i=1 44 55 12 12 12 12 12 42 94 18 06 67 i=2 12 44 55 42 42 42 42 42 94 18 06 67 i=3 12 42 44 55 94 94 94 94 94 18 06 67 i=4 12 42 44 55 94 18 18 18 18 18 06 67 i=5 12 18 42 44 55 94 06 06 06 06 06 67 i=6 06 12 18 42 44 55 94 67 67 67 67 67 i=7 06 12 18 42 44 55 67 94 Сортировка массивов Сортировка 74 При поиске правильной позиции для элемента удобно чередовать сравнения и пересылки, то есть позволять значению x «просеиваться» вниз, при этом сравни% ваем x со следующим элементом a j , а затем либо вставляем x , либо передвигаем a j вправо и переходим влево. Заметим, что есть два разных условия, которые могут вызвать прекращение процесса просеивания: 1. У элемента a j ключ оказался меньше, чем ключ x 2. Обнаружен левый конец последовательности%приемника. PROCEDURE StraightInsertion; (* ADruS2_Sorts *) VAR i, j: INTEGER; x: Item; BEGIN FOR i := 1 TO n–1 DO x := a[i]; j := i; WHILE (j > 0) & (x < a[j–1]) DO a[j] := a[j–1]; DEC(j) END; a[j] := x END END StraightInsertion Анализ простой сортировки вставками. Число сравнений ключей в i %м про% сеивании C i не больше i–1 , как минимум равно 1 и – предполагая, что все пере% становки n ключей равновероятны, – в среднем равно i/2 . Число M i пересылок (присваиваний элементов) равно C i + 1 . Поэтому полные числа сравнений и пере% сылок равны C min = n – 1 M min = 2*(n – 1) C ave = (n 2 – n)/4 M ave = (n 2 + 3n – 4)/4 C max = (n 2 – 3n + 2)/2 M max = (n 2 – n)/2 Минимальные значения получаются, когда элементы изначально упорядоче% ны; наихудший случай имеет место, когда элементы изначально стоят в обратном порядке. В этом смысле сортировка вставками ведет себя вполне естественно. Ясно также, что представленный алгоритм является устойчивой сортировкой: от% носительный порядок элементов с равными ключами не нарушается. Этот алгоритм нетрудно усовершенствовать, заметив, что последователь% ность%приемник a 0 ... a i–1 , в которую нужно вставить новый элемент, уже упоря% дочена. Поэтому можно использовать более быстрый способ нахождения позиции вставки. Очевидный выбор – алгоритм деления пополам, в котором проверяется середина последовательности%приемника и затем продолжаются деления попо% лам, пока не будет найдена точка вставки. Такой модифицированный алгоритм называется сортировкой двоичными вставками: PROCEDURE BinaryInsertion; (* ADruS2_Sorts *) VAR i, j, m, L, R: INTEGER; x: Item; BEGIN FOR i := 1 TO n–1 DO x := a[i]; L := 0; R := i; 75 WHILE L < R DO m := (L+R) DIV 2; IF a[m] <= x THEN L := m+1 ELSE R := m END END; FOR j := i TO R+1 BY –1 DO a[j] := a[j–1] END; a[R] := x END END BinaryInsertion Анализ сортировки двоичными вставками. Позиция вставки найдена, если L = R . Поэтому интервал поиска должен в итоге иметь длину 1; для этого нужно делить интервал длины i пополам log(i) раз. Поэтому C = S S S S Si: 0 ≤ i ≤ n–1: ⎡log(i)⎤ Аппроксимируем эту сумму интегралом Integral (0:n–1) log(x) dx = n*(log(n) – c) + c где c = log(e) = 1/ln(2) = 1.44269... В сущности, число сравнений не зависит от первоначального порядка элемен% тов. Однако из%за округления при делении интервала истинное число сравнений для i элементов может быть на 1 больше, чем ожидается. Причина этого отклоне% ния – в том, что позиции вставки в нижней части последовательности в среднем находятся немного быстрее, чем позиции в верхней части, что благоприятствует тем случаям, когда элементы изначально сильно разупорядочены. На самом деле число сравнений минимально, когда элементы изначально стоят в обратном порядке, и максимально, когда они уже упорядочены. Здесь мы имеем пример неестественного поведения алгоритма сортировки. Тогда число сравнений примерно равно C ≈ n*(log(n) – log(e) ± 0.5) К сожалению, использование двоичного поиска уменьшает только число срав% нений, но не число пересылок. На самом деле пересылки элементов, то есть клю% чей и прочей информации, обычно более затратны, чем сравнение двух ключей, так что получающееся здесь улучшение не принципиально: важная величина M все еще имеет порядок n 2 . Причем сортировка уже упорядоченного массива тре% бует больше времени, чем при использовании простых вставок с последователь% ным поиском. Этот пример показывает, что «очевидное улучшение» вполне может оказаться гораздо менее полезным, чем ожидалось, а в некоторых случаях (которые действительно встречаются) «улучшение» может оказаться и ухудшением. При% ходится заключить, что сортировка вставками не выглядит удачным методом для применения в компьютерных программах: вставка элемента, при которой весь ряд элементов сдвигается только на одну позицию, не является экономной. Лучших результатов можно ожидать от метода, в котором пересылались бы только оди% ночные элементы, причем на более далекие расстояния. Это наблюдение приво% дит к сортировке выбором. Сортировка массивов Сортировка 76 2.2.2. Простая сортировка выбором Данный метод основан на следующей схеме: 1. Выберем элемент с наименьшим ключом. 2. Переставим его с первым элементом a 0 3. Повторим эти операции с остальными n–1 элементами, затем с n–2 элемен% тами.., пока не останется только один – наибольший – элемент. Проиллюстрируем метод на той же последовательности из восьми ключей, что и в табл. 2.1: Таблица 2.2. Таблица 2.2. Таблица 2.2. Таблица 2.2. Таблица 2.2. Пример простой сортировки выбором Начальные ключи: 44 55 12 42 94 18 06 06 06 06 06 67 i=1 06 55 12 12 12 12 12 42 94 18 44 67 i=2 06 12 55 42 94 18 18 18 18 18 44 67 i=3 06 12 18 42 42 42 42 42 94 55 44 67 i=4 06 12 18 42 94 55 44 44 44 44 44 67 i=5 06 12 18 42 44 55 55 55 55 55 94 67 i=6 06 12 18 42 44 55 94 67 67 67 67 67 i=7 06 12 18 42 44 55 67 94 Алгоритм формулируется следующим образом: FOR i := 0 TO n–1 DO присвоить k индекс наименьшего элемента из a i ... a n–1 ; переставить a i и a k END Этот метод можно назвать простой сортировкой выбором. В некотором смысле он противоположен простой сортировке вставками: в последней на каждом шаге, чтобы найти позицию вставки, рассматривается один очередной элемент массива% источника и все элементы массива%приемника; в простой сортировке выбором просматривается весь массив%источник, чтобы найти один элемент с наименьшим ключом, который должен быть вставлен в массив%приемник. PROCEDURE StraightSelection; (* ADruS2_Sorts *) VAR i, j, k: INTEGER; x: Item; BEGIN FOR i := 0 TO n–2 DO k := i; x := a[i]; FOR j := i+1 TO n–1 DO IF a[j] < x THEN k := j; x := a[k] END END; a[k] := a[i]; a[i] := x END END StraightSelection 77 Анализ простой сортировки выбором. Очевидно, число C сравнений ключей не зависит от начального порядка ключей. В этом смысле можно сказать, что этот метод ведет себя не так естественно, как метод простых вставок. Получаем: C = (n 2 – n)/2 Число M пересылок не меньше, чем M min = 3*(n – 1) для изначально упорядоченных ключей, и не больше, чем M max = n 2 /4 + 3*(n – 1), если изначально ключи стояли в обратном порядке. Чтобы определить M avg , бу% дем рассуждать так: алгоритм просматривает массив, сравнивая каждый элемент с наименьшим значением, найденным до сих пор, и если элемент оказывается меньше, чем этот минимум, выполняется присваивание. Вероятность, что второй элемент меньше, чем первый, равна 1/2; такова же и вероятность присваивания минимуму нового значения. Вероятность того, что третий элемент окажется мень% ше, чем первые два, равна 1/3, а вероятность того, что четвертый окажется наи% меньшим, равна 1/4, и т. д. Поэтому полное среднее число пересылок равно H n–1 , где H n – n %ое гармоническое число H n = 1 + 1/2 + 1/3 + ... + 1/n H n можно представить как H n = ln(n) + g + 1/2n – 1/12n 2 + ... где g = 0.577216... – константа Эйлера. Для достаточно больших n можно отбро% сить дробные члены и получить приближенное среднее число присваиваний на i %м проходе в виде F i = ln(i) + g + 1 Тогда среднее число пересылок M avg в сортировке выбором равно сумме величин F i с i , пробегающим от 1 до n : M avg = n*(g+1) + (S S S S Si: 1 ≤ i ≤ n: ln(i)) Аппроксимируя дискретную сумму интегралом Integral (1:n) ln(x) dx = n * ln(n) – n + 1 получаем приближенное выражение M avg = n * (ln(n) + g) Можно заключить, что в общем случае простая сортировка выбором предпоч% тительней простой сортировки вставками, хотя если ключи изначально упорядо% чены или почти упорядочены, простые вставки работают немного быстрее. Сортировка массивов Сортировка 78 2.2.3. Простая сортировка обменами (пузырьковая) Классификация методов сортировки не вполне однозначна. Оба обсуждавшихся выше метода можно также рассматривать как сортировки обменами. Однако сей% час мы представим метод, в котором обмен двух элементов играет главную роль. Получающаяся простая сортировка обменами использует сравнение и обмен пар соседних элементов до тех пор, пока не будут отсортированы все элементы. Как и ранее в простой сортировке выбором, здесь выполняются повторные про% ходы по массиву, причем каждый раз наименьший элемент оставшегося множества просеивается в направлении левого конца массива. Если для разнообразия считать массив расположенным вертикально, а не горизонтально, и вообразить, что элемен% ты – это пузырьки в сосуде с водой, причем их вес равен значению ключа, тогда проходы по массиву приводят к подъему пузырька на уровень, соответствующий его весу (см. табл. 2.3). Такой метод широко известен как пузырьковая сортировка. Таблица 2.3. Таблица 2.3. Таблица 2.3. Таблица 2.3. Таблица 2.3. Пример работы пузырьковой сортировки i = 0 1 2 3 4 5 6 7 44 06 06 06 06 06 06 06 55 44 12 12 12 12 12 12 12 55 44 18 18 18 18 18 42 12 12 12 12 12 55 44 42 42 42 42 94 42 18 18 18 18 18 55 44 44 44 44 18 94 42 42 42 42 42 42 55 55 55 55 06 06 06 06 06 18 18 18 18 18 94 67 67 67 67 67 67 67 67 67 67 67 67 94 94 94 94 94 PROCEDURE BubbleSort; (* ADruS2_Sorts *) VAR i, j: INTEGER; x: Item; BEGIN FOR i := 1 TO n–1 DO FOR j := n–1 TO i BY –1 DO IF a[j–1] > a[j] THEN x := a[j–1]; a[j–1] := a[j]; a[j] := x END END END END BubbleSort Этот алгоритм нетрудно улучшить. Пример в табл. 2.3 показывает, что после% дние три прохода не влияют на порядок элементов, так как они уже отсортирова% ны. Очевидный способ улучшить алгоритм – запомнить, имел ли место хотя бы один обмен во время прохода. Тогда проход без обменов сигнализирует, что алго% 79 ритм может быть остановлен. Однако можно сделать еще одно улучшение, запо% миная не только факт обмена, но и позицию (индекс) последнего обмена. Ясно, например, что все пары соседних элементов левее этого значения индекса (назо% вем его k ) уже упорядочены. Поэтому последующие проходы могут останавли% ваться на этом значении индекса, вместо того чтобы продолжаться до i . Однако внимательный программист заметит любопытную асимметрию: если вначале только один пузырек стоит не на своем месте в «тяжелом» конце, то он доберется до своего места за один проход, а если такой пузырек стоит в «легком» конце, то он будет опускаться в свою правильную позицию только на один шаг за каждый про% ход. Например, массив 12 18 42 44 55 67 94 06 сортируется улучшенной пузырьковой сортировкой за один проход, а массив 94 06 12 18 42 44 55 67 требует семи проходов. Такая неестественная асимметрия наводит на мысль о третьем усовершенствовании: менять направление последовательных проходов. Получающийся алгоритм называют шейкер сортировкой (shaker sort). Его работа показана в табл. 2.4, где он применяется к той же последовательности из восьми ключей, что и в табл. 2.3. PROCEDURE ShakerSort; (* ADruS2_Sorts *) VAR j, k, L, R: INTEGER; x: Item; BEGIN L := 1; R := n–1; k := R; REPEAT FOR j := R TO L BY –1 DO IF a[j–1] > a[j] THEN x := a[j–1]; a[j–1] := a[j]; a[j] := x; k := j END END; L := k+1; FOR j := L TO R BY +1 DO IF a[j–1] > a[j] THEN x := a[j–1]; a[j–1] := a[j]; a[j] := x; k := j END END; R := k–1 UNTIL L > R END ShakerSort |