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

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

cdab

acdb

abcd

В этом методе определяется место в отсортированной части массива, куда должен помещаться элемент. Элементы от данной позиции сдвигаются вверх и на освободившееся место помещается элемент. Трудоемкость алгоритма при линейном поиске n*n/4. Если используется двоичный поиск для определения места элемента, то трудоемкость алгоритма составляет n*log(n). Пример программы, использующей сортировку вставкой элементов массива размерностью k :

void srt2(int *ms, int k)

{ register int i,j,n;

for(i=1;i<k;++i) // индекс элемента для упорядочивания

{ j=i-1; // индекс предыдущего элемента

n=ms[i]; // значение предыдущего элемента

while (j>=0 && n<ms[j])

ms[j--+1]=ms[j]; // сдвиг всех элементов направо

ms[j+1]=n; // запись в освободившийся или в тот же элемент

}

}

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

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

void sort(int *ms, int k)

{ int i,i1,j,m;

for(i=0; i<k-1; i++) // выбор исходного элемента к сравнению

{ i1=i; //

for(j=i+1; j>i; j--) // просмотр массива ”снизу” ”вверх”

if(ms[k]>ms[j]) i1=j; // фиксируем координату элемента в массиве

m=ms[i]; // замена i1 и i элементов

ms[i]=ms[i1];

ms[i1]=m;

}

}

Отмеченные методы сортировки не являются эффективными. В программах, где требуется высокая производительность работы сортировок, применяются следующие методы.

Метод Шелла

Метод был предложен автором (Donald Lewis Shell) в 1959г. Основная идея алгоритма состоит в том, что на начальном этапе реализуется сравнивание и, если требуется, перемещение далеко отстоящих друг от друга элементов. Интервал между сравниваемыми элементами (gap) постепенно уменьшается до единицы, что приводит к перестановке соседних элементов на последних стадиях сортировки (если это необходимо).

Реализуем метод Шелла следующим образом. Начальный шаг сортировки примем равным n/2, т.е. 1/2 от общей длины массива, и после каждого прохода будем уменьшать его в два раза. Каждый этап сортировки включает в себя проход всего массива и сравнение отстоящих на gap элементов. Проход с тем же шагом повторяется, если элементы переставлялись. Заметим, что после каждого этапа отстоящие на gap элементы отсортированы.

Рассмотрим пример. Рассортировать массив чисел: 41,53,11,37,79,19,7,61.

В строке после массива в круглых скобках указаны индексы сравниваемых элементов и указан номер внешнего цикла.

41 53 11 37 79 19 7 61 – исходный массив.

41 19 11 37 79 53 7 61 – (0,4), (1,5) 1-ый цикл

41 19 7 37 79 53 11 61 – (2,6), (3,7)

7 19 41 37 11 53 79 61 – (0,2),(1,3),(2,4),(3,5),(4,6),(5,7) 2-ой цикл

7 19 11 37 41 53 79 61 – (0,2),(1,3),(2,4),(3,5),(4,6),(5,7)

7 11 19 37 41 53 61 79 – сравнивались соседние − 3-ий цикл.

Пример программы, реализующей рассмотренный метод сортировки, приведен ниже:

void sort(int *ms, int k)

{ int i, j, n;

int gap; // шаг сортировки

int flg; // флаг окончания этапа сортировки

for(gap = k/2; gap > 0; gap /= 2)

do

{ flg = 0;

for(i = 0, j = gap; j < k; i++, j++)

if(*(ms+i) > *(ms+j)) // сравниваем отстоящие на gap элементы

{ n = *(ms+j);

*(ms+j) = *(ms+i);

*(ms+i) = n;

flg = 1; // есть еще не рассортированные данные

}

} while (flg); // окончание этапа сортировки

}