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


Алгоритм


     Все элементы условно разделяются на готовую последовательность a1 ... ai-1 и входную ai ... an. На каждом шаге, начиная с i=2 и увеличивая i на 1, берем i-й элемент входной последовательности и вставляем его на нужное место в готовую.

     Пример:

Начальные ключи         44 \\ 55 12 42 94 18 06 67
i = 2
 44 55 \\ 12 42 94 18 06 67
i = 3
 12 44 55 \\ 42 94 18 06 67
i = 4
 12 42 44 55 \\ 94 18 06 67
i = 5
 12 42 44 55 94 \\ 18 06 67
i = 6
 12 18 42 44 55 94 \\ 06 67
i = 7
 06 12 18 42 44 55 94 \\ 67
i = 8
 06 12 18 42 44 55 67 94 \\


     При поиске подходящего места удобно 'просеивать' x, сравнивая его с очередным элементом ai и либо вставляя его, либо пересылая ai направо и продвигаясь налево.

     Просеивание может кончиться при двух условиях:

     1. Найден ai с ключом, меньшим x.

     2. Достигнут конец готовой последовательности.

     Метод хорош устойчивостью сортировки, удобством для реализации в списках и, самое главное, естественностью поведения. То есть уже частично отсортированный массив будут досортирован им гораздо быстрее чем многими 'продвинутыми' методами.

Анализ


Число сравнений
минимальное:
n - 1
среднее:
( n2 + n - 2 ) / 4
максимальное:
( n2 + n ) * / 2 - 1
Количество пересылок
минимальное:
2 * ( n - 1 )
среднее:
( n2 + 9 * n - 10 ) * / 4
максимальное:
( n2 + 3 * n - 4 ) / 2


Пример на Си
Вверх