Цикл по количеству просматриваемых элементов {i:=n, n-1,…, 2}

Найти номер k максимального элемента среди a[1], a[2],…, a[i]

Поменять местами значения элементов a[k] и a[i]

Сортировка обменом (методом пузырька).

Сортировка обменом предусматривает систематический обмен значениями (местами) тех пар, в которых нарушается упорядоченность, до тех пор, пока таких пар не останется.

Алгоритм:

Цикл по количеству просмотров

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

Если < упорядоченность в паре нарушена > то <выполнить обмен значениями >.

Количество просмотров (повторений) во внешнем цикле равно n-1. Оно может быть уменьшено, если i– й шаг показал, что массив уже упорядочен (во внутреннем цикле не было перестановок).

Сортировка включением.

Сортировка основана на следующем: предполагается, что элементы a[1], a[2], …, a [i-1] упорядочены, a[i] вставляется на соответствующее место, не нарушая свойства упорядоченности. Для этого a[i] сравнивается по очереди с a [i-1], a [i-2], …до тех пор, пока не будет обнаружено, что элемент a[i] следует вставить между a[j], a [j-1] (j – номер элемента в a [1…i-1], за которым следует вставить a[i]).Тогда элементы a [j+1],…, a [i-1] сдвигаются на одну позицию вправо, а новая запись помещается в позицию j+1. Удобно совмещать сравнение и перемещение.

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

Метод Шелла

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

Такой метод предложен в 1959 году Дональдом Л. Шеллом [DonaldL. Shell, CACM 2,7 (Java, 1959), 30–32] и известен во всем мире под именем своего автора. Пусть имеется массив записей R1, R2, …., R16.

Делим 16 записей на 8 групп по две записи в каждой группе: (R1, R9), (R2, R10), …., (R8, R16). Сортируем выбранные пары записей в порядке, например, возрастания, т.е. если в паре (R2, R10): R2 > R10, то R2 и R10 меняем местами: R1, R10, R3, R4, R5, R6, R7, R8, R9, R2, R11, R12, R13, R14, R15, R16. То же самое выполняется и для других пар записей.

Это сортировка со смещением 8. Этот процесс называется первым проходом. Разделим теперь записи на четыре группы по четыре записи в каждой: (R1, R5, R9, R13), …, (R4, R8, R12, R16). Затем опять рассортируем каждую группу в отдельности. Это сортировка со смещением 4.

На третьем проходе отсортируем 2 группы по 8 записей: (R1, R3, R5, R7, R9, R11, R13, R15) и (R2, R4, R6, R8, R10, R12, R14, R16). Это сортировка со смещением 2.

Процесс завершается четвёртым проходом, во время которого сортируются все 16 записей. Это сортировка со смещением 1.

В каждой из промежуточных стадий сортировки участвуют либо сравнительно короткие массивы, либо уже сравнительно хорошо упорядоченные массивы, поэтому на каждом этапе можно пользоваться методом простых вставок. Метод сортировки Шелла ещё называется с «убывающим смещением», поскольку каждый проход характеризуется смещением h, таким, что сортируются записи, каждая из которых отстоит от предыдущей на h позиций. Последовательность значений смещений 8, 4, 2, 1 не следует считать неизменной, можно пользоваться любой последовательностью смещений, но последнее смещение должно быть равно 1.

Метод сортировки Шелла также известен под именем Shellsort и метода сортировки с «убывающим смещением», поскольку каждый проход характеризуется смещением h, таким, что сортируются записи, каждая из которых отстоит от предыдущей на h позиции. Последовательность значений смещений 8, 4, 2, 1 не следует считать незыблемой; можно пользоваться любой последовательностью h_{t -1} , h_{t -2} , …, h₀ . но последнее смещение h₀ должно быть равно 1. Например, в таблице 2 продемонстрированная сортировка тех же данных со смещениями 7, 5, 3, 1. Как будет показано ниже, выбор значений смещений на последовательных проходах имеет весьма существенное значение для скорости сортировки.

Сортировка Шелла .