Сортировка «методом пузырька»

Расположим массив сверху вниз, от нулевого элемента - к последнему.

Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами (рис. 6).

Нет обмена	2 «6	2 «7	2 «9	2 «4
4 9 7 6 2 3	4 9 7 2 6 3	4 9 2 7 6 3	4 2 9 7 6 3	2 4 9 7 6 3
Нулевой проход, сравниваемые пары выделены

Рис. 6

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

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

 Среднее число сравнений и обменов имеет квадратичный порядок роста: О(n²),  отсюда можно заключить, что алгоритм «пузырька» очень медленен и малоэффективен. Тем не менее, он прост и его можно улучшать следующим образом:

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

	4 9 7 6 2 3	2 4 9 7 6 3	2 3 4 9 7 6	2 3 4 9 7 6	2 3 4 6 9 7	2 3 4 6 7 9
Номер прохода	i = 0	i = 1	i = 2	i = 3	i = 4	i = 5

Рис. 7

template<class T>void bubbleSort(T a[], long size) { long i, j; T x; for(i=0; i < size; i++) {       // i - номер прохода for(j = size-1; j > i; j--) {  // внутренний цикл прохода if (a[j-1] > a[j]) { x=a[j-1]; a[j-1]=a[j]; a[j]=x; } }}}

Итак, первое улучшение алгоритма заключается в запоминании, производился ли на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу.

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

Качественно другое улучшение алгоритма можно получить из следующего наблюдения. Хотя легкий «пузырек» снизу поднимется наверх за один проход, тяжелые «пузырьки» опускаются с минимальной скоростью: один шаг за итерацию. Так что массив 2 3 4 5 6 1 будет отсортирован за 1 проход, а сортировка последовательности 6 1 2 3 4 5 потребует 5 проходов.

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

template<class T>void shakerSort(T a[], long size) { long j, k = size-1; long lb=1, ub = size-1; // границы неотсортированной части массива T x; do {                                // проход снизу вверх     for(j=ub; j>0; j--) { if (a[j-1] > a[j]) {   x=a[j-1]; a[j-1]=a[j]; a[j]=x;   k=j; } } lb = k+1; for (j=1; j<=ub; j++) { // проход сверху вниз if (a[j-1] > a[j]) {   x=a[j-1]; a[j-1]=a[j]; a[j]=x;   k=j; } } ub = k-1; } while (lb < ub);}

Насколько описанные изменения повлияли на эффективность метода? Среднее количество сравнений, хоть и уменьшилось, но остается O(n²), в то время как число обменов не изменилось. Среднее (оно же худшее) количество операций остается квадратичным.

Дополнительная память не требуется. Поведение усовершенствованного (но не начального) метода довольно естественное, почти отсортированный массив будет отсортирован намного быстрее случайного. Сортировка «пузырьком» устойчива, шейкер-сортировка - нет.

На практике метод «пузырька», даже с улучшениями, работает слишком медленно, поэтому почти не применяется.

Сортировка вставками

Одним из наиболее простых и естественных методов внутренней сортировки является сортировка с простыми включениями или вставками. Идея алгоритма очень проста. Пусть имеется массив ключей 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] (пока не будет достигнута верхняя граница массива).

Аналогичным образом делаются проходы по части массива, и аналогичным же образом в его начале "вырастает" отсортированная последовательность.

Однако в сортировке «пузырьком» или «выбором» можно было четко заявить, что на i -м шаге элементы a[0]...a[i] стоят на правильных местах и никуда более не переместятся. Здесь же подобное утверждение будет более слабым: последовательность a[0]...a[i] упорядочена. При этом по ходу алгоритма в нее будут вставляться все новые элементы.

На i -м шаге работы алгоритма последовательность разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n].

На следующем, (i+1)- м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива. Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним. В зависимости от результата сравнения элемент либо остается на текущем месте (вставка завершена), либо они меняются местами и процесс повторяется (рис. 8).

 

 

0

1

3

4

2

7

9

 

Последовательность на текущий момент. Часть a[0]… a[2] уже упорядочена.

2 ↔ 4	2 ↔ 3	Вставка завершена
0 1 3 2 4 7 9	0 1 2 3 4 7 9	0 1 2 3 4 7 9

Вставка числа 2 в отсортированную подпоследовательность. Сравниваемые пары выделены

Рис. 8

Таким образом, в процессе вставки мы "просеиваем" элемент x к началу массива, останавливаясь в случае, когда:

1) найден элемент, меньший x, или

2) достигнуто начало последовательности.

Иногда этот метод называют сортировкой «просеиванием».

template<class T>void insertSort(T a[], long size) { T x; long i, j; for (i=0; i < size; i++) { // цикл проходов, i - номер прохода x = a[i];                        // поиск места элемента в готовой последовательности     for (j=i-1; j>=0 && a[j] > x; j--) a[j+1] = a[j];              // сдвигаем элемент направо, пока не дошли                                         // место найдено, вставить элемент a[j+1] = x; }}

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

Хорошим показателем сортировки является весьма естественное поведение: почти отсортированный массив будет «досортирован» очень быстро. Именно эти качества алгоритма делают его широко применимым на практике в соответствующих ситуациях.