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

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

ВСТАВКА ПОГРУЖЕНИЕМ: очередной элемент путем ряда обменов " погружается " до требуемой позиции в уже упорядоченную часть массива. Текст ищите в " Вопросах без ответов " .

Существенными в сортировках вставками являются затраты на обмены или сдвиги элементов. Для их уменьшения желательно сначала производить погружение с большим шагом, сразу определяя элемент "по месту". Этим отличается СОРТИРОВКА ШЕЛЛА: исходный массив разбивается на n частей, в каждую из которых попадают элементы с шагом m, начиная от 0,1,...,m-1 соответственно, то есть

.
0 , m , 2m , 3m ,...
1 , m+1, 2m+1, 3m+1,...
2 , m+2, 2m+2, 3m+2,...

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

Содержание раздела