13.9 Быстрая сортировка (метод Хоара)

Метод "пузырька" является не самым эффективным из рассмотренных алгоритмов, поскольку требует большого количества сравнений и обменов. Однако оказалось, что сортировку, основанную на принципе обмена, можно усовершенствовать таким образом, что получится самый хороший из известных на сегодняшний день методов.

Алгоритм быстрой сортировки, предложенный Хоаром, опять-таки использует тот факт, что для достижения наибольшей эффективности желательно производить обмены элементов на больших расстояниях.

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

Далее применим эту же процедуру к более коротким левому и правому подмножествам.

Таким образом, надо реализовать рекурсивный алгоритм, который сортирует элементы множества, начиная с элемента с индексом left и завершая элементом с индексом right. Условие окончания данного алгоритма - совпадение левой и правой границ подмножества (т.е. когда в подмножестве остается один элемент).

Точка деления массива может быть определена следующим образом. Вводятся два указателя i и j, причём вначале а Сравниваются i-й и j-й элементы и, если обмен не требуется, то j=j-1 и этот процесс повторяется. После первого обмена i увеличивается на единицу (i=i+1) и сравнения продолжаются с увеличением i до тех пор, пока не произойдёт ещё один обмен. Тогда опять уменьшим j и т.д. пока не станет i=j. К моменту, когда i=j элемент a_i займёт свою окончательную позицию, так как слева от него не будет больших элементов, а справа - меньших. Таким образом, поставленная задача решена.

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

Пример 13.1. Упорядочить одномерный массив по возрастанию методом обмена. Фрагмент решения данной задачи представлено на рис.13.1а.

Пример 13.2. Рассмотрим задачу сортировки одномерного массива длины n методом обмена в порядке обменов.

При упорядочении можно использовать следующими правилами: числа сравниваются попарно: первое со вторым; второе с третьим; … , i-е с (i + 1); если меньшее стоит в паре на втором месте, то числа меняются местами. За один такой просмотр массива минимальное число перемещается по крайней мере на одно место вверх (вперед), а максимальное – в самый конец. Блок-схема этого алгоритма сортировки показана на рис.13.1б. При сортировке методом "пузырька" выполняется N-1 просмотров, на каждом i-м просмотре производится N-i сравнений. Общее количество С равно N* (N-1)/2,или O(N²).

Три вышеперечисленных метода часто называют прямыми. В них требуется порядка n*n сравнений.

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

а) б)

Рисунок 13.1 – Фрагмент алгоритма сортировки массива методом обменов и выбора

Индивидуальные задания

1) Создать алгоритм сортировки одномерного массива длиной N=50 по убыванию методом обмена.

2) Создать алгоритм сортировки одномерного массива длиной N=55 по возрастанию методом выбора.

3) Имеется одномерный массив длиной N=45. Создать алгоритм сортировки массива по убыванию методом выбора те элементы массива, которые являются четными.

4) Имеется одномерный массив длиной N=70. Создать алгоритм сортировки массива по возрастанию методом выбора те элементы массива, которые располагаются на нечетных позициях.

5) Создать алгоритм сортировки одномерного массива длиной N=29 по убыванию методом выбора.

6) Создать алгоритм сортировки одномерного массива длиной N=37 по возрастанию методом обмена.

7) Создать алгоритм сортировки одномерного массива по убыванию длиной N==44 методом выбора. После упорядочивания в каждой группе повторяющихся элементов оставить один, остальные – удалить.

8) Имеется одномерный массив длиной N=32. Создать алгоритм сортировки массива по возрастанию методом обмена те элементы массива, которые располагаются на нечетных позициях.

9) Имеется одномерный массив длиной N=32. Создать алгоритм сортировки массива по убыванию методом обмена те элементы массива, которые располагаются на нечетных позициях.

10) Имеется одномерный массив длиной N=25. Создать алгоритм так, чтобы упорядочить массив методом выбора, чтобы элементы, находящиеся на четных позициях располагались по возрастанию, а на нечетных – по убыванию.

11) Имеется одномерный массив длиной N=25. Создать алгоритм так, чтобы упорядочить массив методом выбора, чтобы элементы, находящиеся на четных позициях располагались по убыванию, а на нечетных – по возрастанию.

12) Имеется одномерный массив длиной N=25. Создать алгоритм так, чтобы упорядочить массив методом обмена, чтобы элементы, находящиеся на четных позициях располагались по убыванию, а на нечетных – по возрастанию.

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

1) Что понимается под определением сортировка?

2) Укажите основные виды сортировки и их особенности.

3) Приведите пример алгоритма сортировки методом выбора.

4) Приведите пример алгоритма сортировки методом обмена.