Алгоритм сортировки прямым выбором

1. Обнуляем индекс i.

2. Среди элементов a [ i ], a [ i + 1],…, a [ N – 1] находим минимальный элемент и запоминаем его индекс k.

3. Меняем местами элементы a [ i ] и a [ k ], увеличиваем i на единицу.

4. Если i < N – 1 идем на шаг 2.

 

Приведем пример. Заметим, что часть массива, в которой на очередном шаге ищется минимальный элемент, выделена синим цветом, найденный минимальный элемент – красным..

 

 

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

 

 

Блок-схема этой сортировки выглядит следующим образом:

 

 

 

Подсчитаем теперь число сравнений для алгоритма прямого выбора. На первой итерации минимум ищется во всем массиве, то есть требуется N сравнений элементов массива с текущим минимумом (в блок-схеме – min), на второй итерации – (N –1) сравнение, и т. д. На последней итерации требуется одно сравнение. Значит, общее число сравнений есть . Кроме того, если элемент массива оказывается меньше, чем минимум, то переменной min присваивается новое значение. В худшем случае таких присвоений будет также . В конце каждой итерации происходит обмен значений элементов, значит, общее число таких обменов равно числу итераций N. В целом трудоемкость имеет порядок .

 

Сортировка прямой вставкой

 

Сортировка с помощью прямой вставки относится ко второй категории – сортировки с помощью включения. Суть этого метода в следующем: элементы массива просматриваются по одному, и каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов. Другими словами, массив “делится” на две части: упорядоченную (левую) и неупорядоченную (правую). Крайний левый элемент из правой неупорядоченной части вставляется в упорядоченную таким образом, чтобы порядок не нарушился, тем самым, увеличивая упорядоченную левую часть массива и уменьшая правую неупорядоченную. Кроме того, следует иметь в виду, что массив из одного элемента упорядочен. Приведем алгоритм сортировки.