Voidsort(intin[], int n){

for ( int i=0; i < n-1; i++){ // Для очередного i

for ( int j = i + 1, l< = i; j<n; j++) // к - индекс минимального

if (in[j] <in[k]) k=j; // в диапазоне i..n-1

int c=in[k]; in[k] = in[i]; in[i] = c; // Три стакана для очередного

}} // и минимального

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

/ / — " Законспирированная" сортировка выбором

Voidsort(intin[], int n){

for ( int i=0; i < n-1; i++) // Для очередного i

for ( int j = i + 1, k=i; j<n; j++) // Для всех оставшихся

if (in[j] <in[ i]) { // в диапазоне i..n-1

int c=in[i]; in[i] = in[j]; in[j] = c; // сразу же менять с очередным

}} // Выбор совмещен с обменом

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

- до первого, меньше данного (трудоемкость алгоритма пооперациям сравнения - nxii/4), использовать двоичный поиск местав упорядоченной части (трудоемкость алгоритма - nxlog(n)).

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

/ / — Простая вставка

voidsort(intin[], int n){

for ( int i = 1; i < n; i++) { // Для очередного i

int v=in[i]; // Делай 1 : сохранить очередной

for (int k=0; k<i; k++) П Делай 2 : поиск места вставки

if(in[k]>v) break; // перед первым, большим v

for(int j = i - 1 ; j> = k; j - - ) // Делай 3: сдвиг на 1 вправо

in[j + 1] = in[j]; // от очередного до найденного

in[k]=v; // Делай 4 : вставка очередного на место

}} // первого, большего него

В сортировке выбором нет характерных программных контекстов,«ответственных» за вставку: характер программы определяетсяциклом поиска места вставки, который корректно работаеттолько на упорядоченных данных. Таким образом, получаетсязамкнутый круг для логического анализа, разрываемый только доказательствомметодом математической индукции: вставка на i-мшаге выполняется корректно в упорядоченных данных, подготовленныханалогичным i-1-м шагом, и т.д. до 0.

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

// Вставка погружением, подозрительно похожая на обмен

voidsort(intin[],int n) {

for ( int i=1; i<n; i++) // Пока не достигли " дна" или меньшего себя

for ( int k = i; к !=0 &&in[k] <in[k-1]; к--){

int c=in[k]; in[k]=in[k-1]; in[k-1]=c;

}}

Сортировка Шелла. Существенными в сортировках вставкамиявляются затраты на обмены или сдвиги элементов. Для их уменьшенияжелательно сначала производить погружение с большимшагом, сразу определяя элемент «по месту», а затем делать точную«подгонку». Так поступает сортировка Шелла: исходный массивразбивается на m частей, в каждую из которых попадают элементыс шагом т , начиная от 0,1,..., т - 1 соответственно, то есть

0 , m , 2 т , Зт ,...

1 , гл + 1, 2 т + 1, З т + 1 , . . .

2 , т + 2 , 2 т + 2 , З т + 2 , . ..

Каждая часть сортируется отдельно с использованием алгоритмавставок или обмена. Затем выбирается меньший шаг, и алгоритмповторяется. Шаг удобно выбрать равным степеням 2, например,64, 32, 16, 8, 4, 2, 1. Последняя сортировка выполняется с

шагом 1. Несмотря на увеличение числа циклов, суммарное числоперестановок будет меньшим. Принцип сортировки Шелла можноприменить и во всех обменных сортировках.

Замечание. Сортировка Шелла требует четырех вложенныхциклов: по шагу сортировки (по уменьшающимся степеням 2 -m=64, 32, 16 ...)? по группам (по индексу первого элемента в диапазонек=0...т-1), а затем два цикла обычной сортировки погружением

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

Обменная сортировка «пузырьком». Обзор вариантов обменнойсортировки начнем с горячо любимой автором (с методическойточки зрения), но с наименее эффективной простой сортировкиобменом, или сортировки методом «пузырька». Суть еезаключается в следующем: производятся попарное сравнение соседнихэлементов 0-1, 1-2 ... и перестановка, если пара расположенане в порядке возрастания. Просмотр повторяется до тех пор,пока при пробегании массива от начала до конца перестановокбольше не будет.

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