Сортировка выбором

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

Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1)- м.

На i -м шаге выбираем наименьший из элементов a[i]... a[n] и меняем его местами с a[i]. Последовательность шагов при n=5 изображена на рис. 4.

2

2

3

Исходная последовательность

Шаг 0: 2 «4

Шаг 1: 3 «9

2

3

4

2

3

4

6

2

3

4

6

7

Шаг 2: 4 «7

Шаг 3: 6 «6

Шаг 4: 7 «7

Рис. 4

Вне зависимости от номера текущего шага i последовательность a[0]...a[i] (выделена на рисунке курсивом) является упорядоченной. Таким образом, на (n-1)- м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.

template<class T>void selectSort(T a[], long size) { long i, j, k; T x; for(i=0; i < size; i++) { // i - номер текущего шага k=i; x=a[i]; for(j=i+1; j < size; j++) // цикл выбора наименьшего элемента if (a[j] < x) { k=j; x=a[j]; // k - индекс наименьшего элемента } a[k] = a[i]; a[i] = x; // меняем местами наименьший с a[i] }}

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

n + (n-1) + (n-2) + (n-3) +... + 1 = 1/2 * (n²+n) = О(n²).

Таким образом, так как число обменов всегда будет меньше числа сравнений, время сортировки растет квадратично относительно количества элементов.

Алгоритм не использует дополнительной памяти: все операции происходят "на месте".

Для определения устойчивости метода рассмотрим последовательность из трех элементов, каждый из которых имеет два поля, а сортировка идет по первому из них (рис. 5).

a

b

c

a

b

c

Исходная последовательность

Шаг 0: 2 «1

Рис. 5.

Результат сортировки такой последовательности можно увидеть уже после шага 0, так как больше обменов не будет. Порядок ключей 2a, 2b был изменен на 2b, 2a, поэтому метод неустойчив.

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

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

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

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

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

Рис. 6

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

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

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

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

		2	2 3	2 3 4	2 3 4 6	2 3 4 6 7
Номер прохода	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²), в то время как число обменов не изменилось. Среднее (оно же худшее) количество операций остается квадратичным.

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

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

Дата добавления: 2014-12-27