5.3. Пузырьковая сортировка

Метод сортировки, который многие обычно осваивают раньше других из-за его исключительной простоты, называется пузырьковой сортировкой (bubble sort), в рамках которой выполняются следующие действия: проход по массиву с обменом местами соседних элементов, нарушающих заданный порядок, до тех пор, пока массив не будет окончательно отсортирован.

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

В процессе пузырьковой сортировки элементы с малыми значениями устремляются влево. Поскольку сортировка производится в направлении справа налево, каждый элемент меняется местами с элементом слева до тех пор, пока не будет обнаружен элемент с меньшим значением. На первом проходе Е меняется местами с L, Ри М, пока не остановится справа от А; далее уже А продвигается к началу массива, пока не остановится перед другим А, который уже занимает окончательную позицию, i-й по величине элемент устанавливается в свое окончательное положение после i-ого прохода, как и в случае сортировки выбором, но при этом и другие элементы также приближаются к своим окончательным позициям.

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

Алгоритм быстрой сортировки обладает привлекательными особенностями: он принадлежит к категории обменных (in-place) сортировок (т.е., требует всего лишь небольшого вспомогательного стека), на выполнение сортировки N элементов в среднем затрачивается время, пропорциональное N log N и для него характерны исключительно короткие внутренний циклы.

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

Быстрый метод сортировки функционирует по принципу "разделяй и властвуй". Он делит сортируемый массив на две части, затем сортирует эти части независимо друг от друга. Суть метода заключается в процессе разбиения массива, который переупорядочивает массив таким образом, что выполняются следующие условия:

Элемент a[i] для некоторого i занимает свою окончательную позицию в массиве.

Ни один из элементов a[i],..., a[i-l] не превышает a[i].

Ни один из элементов a[i+l],..., а[г] не является меньшим a[i].

Быстрая сортировка представляет собой рекурсивный процесс разбиения массива на части: мы разбиваем его, помещая некоторый (разделяющий) элемент в свою окончательную позицию и выполняем перегруппировку массива таким образом, что элементы, меньшие по значению, остаются слева от разделяющего элемента, а элементы, большие по значению, — справа. Далее мы рекурсивно сортируем левую и правую части массива. Конечным результатом такого вида сортировки является полностью отсортированный массив.

Разбиение осуществляется с использованием следующей стратегии. Прежде всего, в качестве разделяющего элемента произвольно выбирается элемент а[r], лучше чтобы r был ближе к середине — он сразу займет свою окончательную позицию. Далее начинается просмотр с левого конца массива, который продолжается до тех пор, пока не будет найден элемент, превосходящий по значению разделяющий элемент, затем выполняется просмотр, начиная с правого конца массива, который продолжается до тех пор, пока не отыскивается элемент, который по значению меньше разделяющего. Оба элемента, на которых просмотр был прерван, очевидно, находятся не на своих местах в разделенном массиве, и потому они меняются местами. Мы продолжаем дальше в том же духе, пока не убедимся в том, что слева от левого указателя не осталось ни одного элемента, который был бы больше по значению разделяющего, и ни одного элемента справа от правого указателя, которые были бы меньше по значению разделяющего элемента.

Листинг: Алгоритм быстрой сортировки

// Шаблон quicksort задает рекурсивную функцию сортировки

// элементов массива методом быстрой сортировки.

// - Key - класс, задающий тип элементов массива;

// - array - упорядочиваемый массив;

// -.low, high - индексы, задающие диапазон сортировки.

template <class Кеу>

void quicksort(Key * array, int low, int high) {

// Предполагается, что в начале работы low <= high

// В результате сортировки получается упорядоченный фрагмент

// массива в диапазоне от low до high

int pLow = low,

pHigh - high; // указатели концов фрагмента массива

Key elem = array[low]; // выбранный произвольный элемент

while (pLow != pHigh) {

// 1. Просмотр элементов массива снизу

while (pHigh > pLow && array[pHigh] >= elem) pHigh--;

if (pHigh > pLow) {

array[pLow] =array[pHigh]; // Обмен местами элементов

// 2. Просмотр элементов массива "сверху"

while (pLow < pHigh && array[pLow] <= elem) pLow++;

array[pHigh] = array [pLow]; // Еще один обмен

}

}

// Теперь указатели pLow и pHigh столкнулись, массив разделен,

array[pLow] = elem;

// Далее следуют рекурсивные вызовы функции для двух половинок

if (pLow - low > 1) quickSort<Key>(array, low, pLow-1);

if (high - pHigh > 1) quickSort<Key>(array, pHigh+1, high);

}