Лекция № 3

Тема: «Улучшенные алгоритмы сортировки»

План лекции

1. Метод Шелла

2. Быстрая сортировка

3. Сортировка слиянием

Улучшенные алгоритмы сортировки

Все алгоритмы, рассмотренные в предыдущей лекции, имеют один фатальный недостаток — время их выполнения имеет порядок n². Это делает сортировку больших объемов данных очень медленной. По существу, в какой-то момент эти алгоритмы становятся слишком медленными, чтобы их применять. К сожалению, страшные истории о "сортировках, которые продолжались три дня", зачастую реальны. Когда сортировка занимает слишком много времени, причиной этому обычно является неэффективность использованного в ней алгоритма. Тем не менее, первой реакцией в такой ситуации часто становится оптимизация кода вручную, возможно, путем переписывания его на ассемблере. Несмотря на то, что ручная оптимизация иногда ускоряет процедуру на постоянный множитель, если алгоритм сортировки не эффективен, сортировка всегда будет медленной независимо от того, насколько оптимально написан код. Следует помнить, если время работы процедуры пропорционально n², то увеличение скорости кода или компьютера даст лишь небольшое улучшение, поскольку время выполнения увеличивается как n². Существует правило: если используемый в программе алгоритм слишком медленный сам по себе, никакой объем ручной оптимизации не сделает программу достаточно быстрой. Решение заключается в применении лучшего алгоритма сортировки.

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

1. Сортировка методом Шелла

Метод Шелла является усовершенствованием метода простого включения, который основан на том, что включение использует любой частичный порядок. Но недостатком простого включения является то, что во внутреннем цикле элемент A[i] фактически сдвигается на одну позицию. И так до тех пор, пока он не достигнет своего места в отсортированной части. (На самом деле передвигалось место, оставленное под A[i]). Метод Шелла позволяет преодолеть это ограничение следующим интересным способом (рис. 3).

Вместо включения A[i] в подмассив предшествующих ему элементов, его включают в подсписок, содержащий элементы A[i – h], A[i – 2h], A[i – 3h] и так далее, где h – положительная константа. Таким образом, формируется массив, в котором «h-серии» элементов, отстоящие друг от друга на h, сортируются отдельно.

Конечно, этого недостаточно: процесс возобновляется с новым значением h, меньшим предыдущего. И так до тех пор, пока не будет достигнуто значение h = 1.

В настоящее время неизвестна последовательность hi, h_i–1, h_i–2, ...,h₁, оптимальность которой доказана. Для достаточно больших массивов рекомендуемой считается такая последовательность, что h_i+1 = 3h_i+1,а h₁ = 1. Начинается процесс с h_m, что h_m ≥ [n/9]. Иногда значение h вычисляют проще: h_i+1 = h_i/2, h₁ = 1, h_m = n/2. Это упрощенное вычисление h и будем использовать далее.

Теперь запишем алгоритм:

procedure ShellSort(n: integer;

var A: array[1..n] of integer);

{Процедура сортировки Шелла}

var

h, i, j, Tmp: integer;

begin

{Вычисляем величину h}

h := n div 2;

{Собственно сортировка}

while h > 0 do begin

for i := 1 to n-h do

begin

j := i;

{Сравниваем элементы, отстоящие друг от друга}

{на расстояние, кратное h}

while (j > 0) and (A[j] > A[j+h]) do

begin

{Меняем элементы}

Tmp := A[j+h];

A[j+h] := A[j];

A[j] := Tmp;

j := j – h;

end;

end;

{Уменьшаем размер серии}

h := h div 2;

end;

end;

Рисунок 3 – Сортировка Шелла

Как показывают теоретические выкладки сортировке методом Шелла требуется в среднем 1,66n^1,25 перемещений. Порядок элементов влияет на количество итераций внутреннего цикла while. Дополнительной памяти данный алгоритм не требует, но и не гарантирует сохранение порядка элементов с одинаковыми значениями.

1. Быстрая сортировка (Хоара)

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

Этот алгоритм является ярким примером реализации принципа «разделяй и властвуй». Как показывают теоретические выкладки, наиболее эффективным в общем случае оказывается разделение задачи на две равные по сложности части, что здесь и делается. На каждом шаге алгоритма сначала выбирается «средний» элемент, затем переставляются элементы массива так, что массив разделился на две части. Первая часть содержит элементы меньше «среднего» и, возможно, равные ему. Вторая часть содержит элементы больше «среднего» и, возможно, равные ему. После такого деления массива остается только отсортировать его части по отдельности, с которыми поступаем аналогично (делим на две части). И так до тех пор, пока эти части не окажутся состоящими из одного элемента, а массив из одного элемента всегда отсортирован (рис. 6). В случае, когда массив содержит только одинаковые элементы, выбор «среднего» элемента не производится и сортировка не осуществляется.

Рисунок 6 – Сортировка Хоара

Разделение массива на две части производится следующим образом. Устанавливаем один курсор на левую границу массива, а второй – на правую границу. Затем осуществляем перемещение курсоров навстречу друг другу до тех пор, пока они не пересекутся. При перемещении курсоров сравниваем значения текущих элементов со «средним». Находим левый текущий элемент, больший «среднего», и правый текущий элемент, меньший «среднего» (т. е. элементы, которые находятся «не на своем месте»). Осуществляем обмен этих элементов.

Заметим, что предложенный способ нахождения «среднего» элемента подмассива в худшем случае приведет к тому, что после деления, например, правая часть поделенного массива будет содержать один элемент, а левая – все остальные. В этом случае получается порядка n рекурсивных вызовов. Это значит, что необходимо будет завести дополнительную память размером, пропорциональным n, и пространственная сложность V_max(n) будет пропорциональна O(n). В среднем и лучшем случае, можно говорить о пространственной сложности, пропорциональной O(log n).

В худшем случае этот алгоритм дает временную сложность T_max(n), пропорциональную O(n²) (для случая, когда все выборки «среднего» элемента оказались неудачны), но как показывают теоретические исследования, вероятность такого случая очень мала. В среднем же и в лучшем случае получим временную сложность T(n), пропорциональную O(nlog n).

2. Сортировка слиянием

Этот метод сортирует массив последовательным слиянием пар уже отсортированных подмассивов. Пусть k – положительное целое число. Разобьем массив A[1]...A[n] на участки длины k. (Первый – A[1]...A[k], затем A[k+1]...A[2k] и т. д.) Последний участок будет неполным, если n не делится нацело на k.

Назовем массив k-упорядоченным, если каждый из этих участков длины k упорядочен. Ясно, что любой массив 1-упорядочен, так как его участки длиной 1 можно считать упорядоченными. Если массив k-упорядочен и n ≤ k, то он упорядочен.

Рассмотрим процедуру преобразования k-упорядоченного массива в 2k-упорядоченный. Сгруппируем все участки длины k в пары участков. Теперь пару упорядоченных участков сольем в один упорядоченный участок. Проделав это со всеми парами, получим 2k-упорядоченный массив (рис. 7).

Рисунок 7– Сортировка слиянием

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

Сразу же бросается в глаза недостаток алгоритма – он требует дополнительную память размером порядка n (для хранения вспомогательного массива). Кроме того, он не гарантирует сохранение порядка элементов с одинаковыми значениями. Но его временная сложность всегда пропорциональна O(nlog n) (так как преобразование k-упорядоченного массива в 2k-упорядоченный требует порядка n действий и внешний цикл по k совершает порядка log n итераций).

Контрольные вопросы.

1. Что такое «сортировка»?

2. Сколько существует групп алгоритмов сортировки?

3. Какие существуют алгоритмы сортировки?

4. По каким признакам характеризуются алгоритмы сортировки?

5. Что нужно учитывать при выборе алгоритма сортировки?

6. Какой алгоритм сортировки считается самым простым?

7. Какой алгоритм сортировки считается самым эффективным?

8. Что означает понятие «скорость сортировки»?

9. В чем заключается метод быстрой сортировки?

10. В чем заключается метод сортировки Шелла?

11. В чем заключается метод сортировки слиянием?