Сортировка разделением (Quicksort)




Методы внутренней сортировки

В этой и следующей частях книги мы будем обсуждать методы сортировки информации. В общей постановке задача ставится следующим образом. Имеется последовательность однотипных записей, одно из полей которых выбрано в качестве ключевого (далее мы будем называть его ключом сортировки). Тип данных ключа должен включать операции сравнения ("=", ">", "<", ">=" и "<="). Задачей сортировки является преобразование исходной последовательности в последовательность, содержащую те же записи, но в порядке возрастания (или убывания) значений ключа. Метод сортировки называется устойчивым, если при его применении не изменяется относительное положение записей с равными значениями ключа.

Различают сортировку массивов записей, целиком расположенных в основной памяти (внутреннюю сортировку), и сортировку файлов, хранящихся во внешней памяти и не помещающихся полностью в основной памяти (внешнюю сортировку). Для внутренней и внешней сортировки требуются существенно разные методы. В этой части мы рассмотрим наиболее известные методы внутренней сортировки, начиная с простых и понятных, но не слишком быстрых, и заканчивая не столь просто понимаемыми усложненными методами.

Естественным условием, предъявляемым к любому методу внутренней сортировки является то, что эти методы не должны требовать дополнительной памяти: все перестановки с целью упорядочения элементов массива должны производиться в пределах того же массива. Мерой эффективности алгоритма внутренней сортировки являются число требуемых сравнений значений ключа (C) и число перестановок элементов (M).

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

Сортировка включением

Одним из наиболее простых и естественных методов внутренней сортировки является сортировка с простыми включениями. Идея алгоритма очень проста. Пусть имеется массив ключей a[1], a[2],..., a[n]. Для каждого элемента массива, начиная со второго, производится сравнение с элементами с меньшим индексом (элемент a[i] последовательно сравнивается с элементами a[i-1], a[i-2]...) и до тех пор, пока для очередного элемента a[j] выполняется соотношение a[j] > a[i], a[i] и a[j] меняются местами. Если удается встретить такой элемент a[j], что a[j] <= a[i], или если достигнута нижняя граница массива, производится переход к обработке элемента a[i+1] (пока не будет достигнута верхняя граница массива).

Легко видеть, что в лучшем случае (когда массив уже упорядочен) для выполнения алгоритма с массивом из n элементов потребуется n-1 сравнение и 0 пересылок. В худшем случае (когда массив упорядочен в обратном порядке) потребуется n?(n-1)/2 сравнений и столько же пересылок. Таким образом, можно оценивать сложность метода простых включений как O(n2).

Можно сократить число сравнений, применяемых в методе простых включений, если воспользоваться тем фактом, что при обработке элемента a[i] массива элементы a[1], a[2],..., a[i-1] уже упорядочены, и воспользоваться для поиска элемента, с которым должна быть произведена перестановка, методом двоичного деления. В этом случае оценка числа требуемых сравнений становится O(n?log n). Заметим, что поскольку при выполнении перестановки требуется сдвижка на один элемент нескольких элементов, то оценка числа пересылок остается O(n2).

Таблица 2.1 Пример сортировки методом простого включения

Начальное состояние массива 8 23 5 65 44 33 1 6
Шаг 1 8 23 5 65 44 33 1 6
Шаг 2 8 5 23 65 44 33 1 65 8 23 65 44 33 1 6
Шаг 3 5 8 23 65 44 33 1 6
Шаг 4 5 8 23 44 65 33 1 6
Шаг 5 5 8 23 44 33 65 1 65 8 23 33 44 65 1 6
Шаг 6 5 8 23 33 44 1 65 65 8 23 33 1 44 65 65 8 23 1 33 44 65 65 8 1 23 33 44 65 65 1 8 23 33 44 65 61 5 8 23 33 44 65 6
Шаг 7 1 5 8 23 33 44 6 651 5 8 23 33 6 44 651 5 8 23 6 33 44 651 5 8 6 23 33 44 651 5 6 8 23 33 44 65

Дальнейшим развитием метода сортировки с включениями является сортировка методом Шелла, называемая по-другому сортировкой включениями с уменьшающимся расстоянием. Мы не будем описывать алгоритм в общем виде, а ограничимся случаем, когда число элементов в сортируемом массиве является степенью числа 2. Для массива с 2n элементами алгоритм работает следующим образом. На первой фазе производится сортировка включением всех пар элементов массива, расстояние между которыми есть 2(n-1). На второй фазе производится сортировка включением элементов полученного массива, расстояние между которыми есть 2(n-2). И так далее, пока мы не дойдем до фазы с расстоянием между элементами, равным единице, и не выполним завершающую сортировку с включениями. Применение метода Шелла к массиву, используемому в наших примерах, показано в таблице 2.2.

Таблица 2.2. Пример сортировки методом Шелл

Начальное состояние массива 8 23 5 65 44 33 1 6
Фаза 1 (сортируются элементы, расстояние между которыми четыре) 8 23 5 65 44 33 1 68 23 5 65 44 33 1 68 23 1 65 44 33 5 68 23 1 6 44 33 5 65
Фаза 2 (сортируются элементы, расстояние между которыми два) 1 23 8 6 44 33 5 65 1 23 8 6 44 33 5 65 1 23 8 6 5 33 44 65 1 23 5 6 8 33 44 65 1 6 5 23 8 33 44 651 6 5 23 8 33 44 651 6 5 23 8 33 44 65
Фаза 3 (сортируются элементы, расстояние между которыми один) 1 6 5 23 8 33 44 651 5 6 23 8 33 44 651 5 6 23 8 33 44 651 5 6 8 23 33 44 651 5 6 8 23 33 44 651 5 6 8 23 33 44 651 5 6 8 23 33 44 65

В общем случае алгоритм Шелла естественно переформулируется для заданной последовательности из t расстояний между элементами h1, h2,..., ht, для которых выполняются условия h1 = 1 и h(i+1) < hi. Дональд Кнут показал, что при правильно подобранных t и h сложность алгоритма Шелла является O(n(1.2)), что существенно меньше сложности простых алгоритмов сортировки.

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

Простая обменная сортировка (в просторечии называемая "методом пузырька") для массива a[1], a[2],..., a[n] работает следующим образом. Начиная с конца массива сравниваются два соседних элемента (a[n] и a[n-1]). Если выполняется условие a[n-1] > a[n], то значения элементов меняются местами. Процесс продолжается для a[n-1] и a[n-2] и т.д., пока не будет произведено сравнение a[2] и a[1]. Понятно, что после этого на месте a[1] окажется элемент массива с наименьшим значением. На втором шаге процесс повторяется, но последними сравниваются a[3] и a[2]. И так далее. На последнем шаге будут сравниваться только текущие значения a[n] и a[n-1]. Понятна аналогия с пузырьком, поскольку наименьшие элементы (самые "легкие") постепенно "всплывают" к верхней границе массива. Пример сортировки методом пузырька показан в таблице 2.3.

Таблица 2.3. Пример сортировки методом пузырька

Начальное состояние массива 8 23 5 65 44 33 1 6
Шаг 1 8 23 5 65 44 33 1 68 23 5 65 44 1 33 68 23 5 65 1 44 33 68 23 5 1 65 44 33 68 23 1 5 65 44 33 68 1 23 5 65 44 33 61 8 23 5 65 44 33 6
Шаг 2 1 8 23 5 65 44 6 331 8 23 5 65 6 44 331 8 23 5 6 65 44 331 8 23 5 6 65 44 331 8 5 23 6 65 44 331 5 8 23 6 65 44 33
Шаг 3 1 5 8 23 6 65 33 441 5 8 23 6 33 65 441 5 8 23 6 33 65 441 5 8 6 23 33 65 441 5 6 8 23 33 65 44
Шаг 4 1 5 6 8 23 33 44 65 1 5 6 8 23 33 44 65 1 5 6 8 23 33 44 65 1 5 6 8 23 33 44 65
Шаг 5 1 5 6 8 23 33 44 65 1 5 6 8 23 33 44 65 1 5 6 8 23 33 44 65
Шаг 6 1 5 6 8 23 33 44 65 1 5 6 8 23 33 44 65
Шаг 7 1 5 6 8 23 33 44 65

Для метода простой обменной сортировки требуется число сравнений n?(n-1)/2, минимальное число пересылок 0, а среднее и максимальное число пересылок - O(n2).

Метод пузырька допускает три простых усовершенствования. Во-первых, как показывает таблица 2.3, на четырех последних шагах расположение значений элементов не менялось (массив оказался уже упорядоченным). Поэтому, если на некотором шаге не было произведено ни одного обмена, то выполнение алгоритма можно прекращать. Во-вторых, можно запоминать наименьшее значение индекса массива, для которого на текущем шаге выполнялись перестановки. Очевидно, что верхняя часть массива до элемента с этим индексом уже отсортирована, и на следующем шаге можно прекращать сравнения значений соседних элементов при достижении такого значения индекса. В-третьих, метод пузырька работает неравноправно для "легких" и "тяжелых" значений. Легкое значение попадает на нужное место за один шаг, а тяжелое на каждом шаге опускается по направлению к нужному месту на одну позицию.

На этих наблюдениях основан метод шейкерной сортировки (ShakerSort). При его применении на каждом следующем шаге меняется направление последовательного просмотра. В результате на одном шаге "всплывает" очередной наиболее легкий элемент, а на другом "тонет" очередной самый тяжелый. Пример шейкерной сортировки приведен в таблице 2.4.

Таблица 2.4. Пример шейкерной сортировки

Начальное состояние массива 8 23 5 65 44 33 1 6
Шаг 1 8 23 5 65 44 33 1 68 23 5 65 44 1 33 68 23 5 65 1 44 33 68 23 5 1 65 44 33 68 23 1 5 65 44 33 68 1 23 5 65 44 33 61 8 23 5 65 44 33 6
Шаг 2 1 8 23 5 65 44 33 61 8 5 23 65 44 33 61 8 5 23 65 44 33 61 8 5 23 44 65 33 61 8 5 23 44 33 65 61 8 5 23 44 33 6 65
Шаг 3 1 8 5 23 44 6 33 651 8 5 23 6 44 33 651 8 5 6 23 44 33 651 8 5 6 23 44 33 651 5 8 6 23 44 33 65
Шаг 4 1 5 6 8 23 44 33 651 5 6 8 23 44 33 651 5 6 8 23 44 33 651 5 6 8 23 33 44 65
Шаг 5 1 5 6 8 23 33 44 651 5 6 8 23 33 44 651 5 6 8 23 33 44 65

Шейкерная сортировка позволяет сократить число сравнений (по оценке Кнута средним числом сравнений является (n2 - n?(const + ln n)), хотя порядком оценки по-прежнему остается n2. Число же пересылок, вообще говоря, не меняется. Шейкерную сортировку рекомендуется использовать в тех случаях, когда известно, что массив "почти упорядочен".

Сортировка выбором

При сортировке массива a[1], a[2],..., a[n] методом простого выбора среди всех элементов находится элемент с наименьшим значением a[i], и a[1] и a[i] обмениваются значениями. Затем этот процесс повторяется для получаемых подмассивов a[2], a[3],..., a[n],... a[j], a[j+1],..., a[n] до тех пор, пока мы не дойдем до подмассива a[n], содержащего к этому моменту наибольшее значение. Работа алгоритма иллюстрируется примером в таблице 2.5.

Таблица 2.5. Пример сортировки простым выбором

Начальное состояние массива 8 23 5 65 44 33 1 6
Шаг 1 1 23 5 65 44 33 8 6
Шаг 2 1 5 23 65 44 33 8 6
Шаг 3 1 5 6 65 44 33 8 23
Шаг 4 1 5 6 8 44 33 65 23
Шаг 5 1 5 6 8 33 44 65 23
Шаг 6 1 5 6 8 23 44 65 33
Шаг 7 1 5 6 8 23 33 65 44
Шаг 8 1 5 6 8 23 33 44 65

Для метода сортировки простым выбором требуемое число сравнений - n?(n-1)/2. Порядок требуемого числа пересылок (включая те, которые требуются для выбора минимального элемента) в худшем случае составляет O(n2). Однако порядок среднего числа пересылок есть O(n?ln n), что в ряде случаев делает этот метод предпочтительным.

Сортировка разделением (Quicksort)

Метод сортировки разделением был предложен Чарльзом Хоаром (он любит называть себя Тони) в 1962 г. Этот метод является развитием метода простого обмена и настолько эффективен, что его стали называть "методом быстрой сортировки - Quicksort".

Основная идея алгоритма состоит в том, что случайным образом выбирается некоторый элемент массива x, после чего массив просматривается слева, пока не встретится элемент a[i] такой, что a[i] > x, а затем массив просматривается справа, пока не встретится элемент a[j] такой, что a[j] < x. Эти два элемента меняются местами, и процесс просмотра, сравнения и обмена продолжается, пока мы не дойдем до элемента x. В результате массив окажется разбитым на две части - левую, в которой значения ключей будут меньше x, и правую со значениями ключей, большими x. Далее процесс рекурсивно продолжается для левой и правой частей массива до тех пор, пока каждая часть не будет содержать в точности один элемент. Понятно, что как обычно, рекурсию можно заменить итерациями, если запоминать соответствующие индексы массива. Проследим этот процесс на примере нашего стандартного массива (таблица 2.6).

Таблица 2.6. Пример быстрой сортировки

Начальное состояние массива 8 23 5 65 |44| 33 1 6
Шаг 1 (в качестве x выбирается a[5]) |--------|8 23 5 6 44 33 1 65 |---|8 23 5 6 1 33 44 65
Шаг 2 (в подмассиве a[1], a[5] в качестве x выбирается a[3]) 8 23 |5| 6 1 33 44 65|--------|1 23 5 6 8 33 44 65 |--|1 5 23 6 8 33 44 65
Шаг 3 (в подмассиве a[3], a[5] в качестве x выбирается a[4]) 1 5 23 |6| 8 33 44 65 |----|1 5 8 6 23 33 44 65
Шаг 4 (в подмассиве a[3], a[4] выбирается a[4]) 1 5 8 |6| 23 33 44 65 |--|1 5 6 8 23 33 44 65

Алгоритм недаром называется быстрой сортировкой, поскольку для него оценкой числа сравнений и обменов является O(n?log n). На самом деле, в большинстве утилит, выполняющих сортировку массивов, используется именно этот алгоритм.

 

 


Рис. 2.14.

Для сортировки со слиянием массива a[1], a[2],..., a[n] заводится парный массив b[1], b[2],..., b[n]. На первом шаге производится слияние a[1] и a[n] с размещением результата в b[1], b[2], слияние a[2] и a[n-1] с размещением результата в b[3], b[4],..., слияние a[n/2] и a[n/2+1] с помещением результата в b[n-1], b[n]. На втором шаге производится слияние пар b[1], b[2] и b[n-1], b[n] с помещением результата в a[1], a[2], a[3], a[4], слияние пар b[3], b[4] и b[n-3], b[n-2] с помещением результата в a[5], a[6], a[7], a[8],..., слияние пар b[n/2-1], b[n/2] и b[n/2+1], b[n/2+2] с помещением результата в a[n-3], a[n-2], a[n-1], a[n]. И т.д. На последнем шаге, например (в зависимости от значения n), производится слияние последовательностей элементов массива длиной n/2 a[1], a[2],..., a[n/2] и a[n/2+1], a[n/2+2],..., a[n] с помещением результата в b[1], b[2],..., b[n].

Для случая массива, используемого в наших примерах, последовательность шагов показана в таблице 2.9.

Таблица 2.9. Пример сортировки со слиянием

Начальное состояние массива 8 23 5 65 44 33 1 6
Шаг 1 6 8 1 23 5 33 44 65
Шаг 2 6 8 44 65 1 5 23 33
Шаг 3 1 5 6 8 23 33 44 65

При применении сортировки со слиянием число сравнений ключей и число пересылок оценивается как O(n?log n). Но следует учитывать, что для выполнения алгоритма для сортировки массива размера n требуется 2?n элементов памяти.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-12-12 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: