Быстрые сортировки

Сортирующее действие

Предположим следующую задачу: имеется два отсортированных по возрастанию массива A и B, необходимо составить из них массив C, который также отсортирован по возрастанию.

Для решения этой задачи можно воспользоваться слиянием.

Размер массива C известен - это сумма размеров массивов A и B. Завёдем три индекса:

• a будет указывать на позицию в массиве A
• b - на позицию в массиве B
• c - на позицию в массиве C

В начале каждый из индексов указывает на начало своего массива.

Будем класть в C[c] элемент, нестрого меньший (для устойчивости сортировки) из A[a] и B[b]. Если в результате этой операции мы взяли элемент из A, то передвинем позицию a вправо на единицу, аналогично поступаем, если взяли элемент из B. Также, в любом случае, передвинем уровень заполнения c.

Такое заполнение закончится тогда, когда мы выйдем за пределы одно из сливаемых массивов.

Для завершения слияния необходимо дополнить C нетронутыми элементами, которые будут находится в одном из массивов, так как второй мы израсходовали.

Сортировка

Итак, мы знаем, как получить отсортированный массив из двух отсортированных.

Сортировка слиянием заключается в том, чтобы

• разбить исходный массив пополам
• рекуррентно отсортировать левую часть
• рекуррентно отсортировать правую часть
• осуществить слияние отсортированных частей в исходный массив

Крайний случай это массив длины 0 или 1, поскольку он уже отсортирован.

Сортирующее действие

Сортирующим действием сортировки Тони Хоара является разбиение массива по барьеру.

В результате его применения элементы в исходном массиве должны быть упорядочены следующим образом:

• в начале расположены элементы, меньшие барьера (группа 1)
• затем идут элементы, равные барьеру (группа 2)
• а после них следуют элементы, большие барьера (группа 3)

Сортировка

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

Крайним случаем являются массивы длиной 0 и 1.