Алгоритм сортировки прямой вставкой

1. Начинаем со второго элемента, т.е. полагаем i = 1.

2. Выбираем очередной элемент a [ i ] из неупорядоченной части массива.

3. Просматривая последовательно элементы из упорядоченной части и сравнивая их с a [ i ], находим место для i -го элемента.

4. Все элементы из левой части, большие a [ i ], сдвигаем на 1 позицию вправо; на освободившееся место ставится элемент a [ i ].

5. Если i < N – 1, увеличиваем i на единицу и идем на шаг 2.

 

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

 

 

В реальном процессе поиска подходящего места для вставляемого элемента x удобно начинать просмотр упорядоченной части массива с “конца”, сравнивать x с очередным элементом a [ j ], а затем либо вставлять элемент x на место, либо a [ j ] сдвигать вправо.

 

Теперь приведем блок-схему сортировки с помощью прямой вставки.

 

 

Заметим, что процесс поиска подходящего места заканчивается при выполнении одного из двух условий:

1. найден элемент a [j], меньший или равный вставляемому элементу x;

2. достигнут левый конец упорядоченной части массива.

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

Попробуем улучшить сортировку. Такой типичный случай повторяющегося процесса с двумя условиями окончания позволяет нам воспользоваться уже известным приемом добавления “барьера”. (Вставить ссылку на поиск с барьером). Применим его, поставив барьер со значением x в начало массива, т.е. положив a [0] = x (напомним, что для этого необходимо увеличить размер массива на 1, а сам массив располагать со второй позиции, т.е. с a [1]). Приведем блок-схему сортировки с помощью прямой вставки с барьером.

 

 

Сортировка прямой вставкой с барьером устойчива.

Однако, барьер – не единственное улучшение. Обратим внимание на то, что левая часть массива упорядочена. В этом случае было бы логично при поиске места для вставки элемента x использовать метод двоичного поиска (см. п.1.2.), а затем сдвинуть часть упорядоченного массива на одну позицию вправо. Такой модифицированный алгоритм называется прямой вставкой с бинарным поиском. (вставить ссылку на бинарный поиск).

Напомним суть метода бинарного поиска. Делим упорядоченную часть массива пополам. Сравниваем срединный элемент a [ m ] с элементом x. Если x меньше срединного элемента, то искать место для x следует в левой от a [ m ] части массива, т.е. сдвигаем правую границу, в противном случае место для x следует искать в правой от a [ m ] упорядоченной части массива, т.е. сдвигаем левую границу. Снова делим получившуюся упорядоченную часть массива пополам и т.д.

Таким образом, мы разбили алгоритм на 2 части: поиск места для вставляемого элемента и сдвиг части массива (освободить место для вставляемого элемента).

Приведем блок-схему этого алгоритма. Здесь: N – размерность массива, L – индекс левой границы, R – индекс правой границы.

 

 

Сортировка прямой вставкой с двоичным поиском неустойчива.

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

 

 

Сортировка «пузырек»

 

Сортировка методом “пузырек” относится к третьей категории – сортировки с помощью обменов. Суть этого метода в следующем: если два рядом стоящих элемента расположены не по порядку, то они меняются местами. Процесс повторяется до тех пор, пока массив не будет упорядочен. Другими словами, просматривается массив, и элементы сравниваются попарно: a [ i ] с a [ i + 1]. Если a [ i ] больше a [ i + 1], то элементы обмениваются значениями. В результате одного просмотра самый большой, “тяжелый” элемент сместится на последнюю позицию. Опять начинаем просмотр массива с начала и т.д.