Алгоритм
Все элементы условно разделяются на готовую последовательность a1 ... ai-1 и входную ai ... an. Hа каждом шаге, начиная с i=2 и увеличивая i на 1, берем i-й элемент входной последовательности и вставляем его на нужное место в готовую.
Пример:
Hачальные ключи 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 направо и продвигаясь налево.
Просеивание может кончиться при двух условиях:
Hайден ai с ключом, меньшим x.
Достигнут конец готовой последовательности.
Метод хорош устойчивостью сортировки, удобством для реализации в списках и, самое главное, естественностью поведения. То есть уже частично отсортированный массив будут досортирован им гораздо быстрее чем многими 'продвинутыми' методами.
Анализ
| Число сравнений | минимальное: n - 1
среднее: ( n^2 + n - 2 ) / 4
максимальное: ( n^2 + n ) * / 2 - 1 | | Количество пересылок | минимальное: 2 * ( n - 1 )
среднее: ( n^2 + 9 * n - 10 ) / 4
максимальное: ( n^2 + 3 * n - 4 ) / 2 |
Примечания.
Если мы работаем с массивом, а не списком, то искать место вставки очередного ai в готовую последовательность можно бинарным поиском,
ведь a1..a_i-1 уже отсортированы! При этом количество сравнений снизится до O(nlogn), но сортировка станет вести себя крайне неестественно (уже
отсортированный массив обрабатывается дольше всего), а, самое главное, количество пересылок по-прежнему останется O(n^2).
При работе с массивами можно использовать и другое улучшение InsertSort'a - ShellSort (описана в другом вопросе).
Пример на Си - Tomas Niemann.
typedef int item; /* Тип сортируемых элементов */
typedef int tblIndex; /* Тип ключей, по которым сортируем */
#define compGT(a,b) (a > b) /* Функция сравнения */
void insertSort(T *a, tblIndex lb, tblIndex ub) {
item t;
tblIndex i, j;
/***********************
* сортируем a[lb..ub] *
***********************/
for (i = lb + 1; i <= ub; i++) {
t = a[i];
/* Сдвигаем элементы вниз, пока */
/* не найдем место вставки. */
for (j = i-1; j >= lb && compGT(a[j], t); j--)
a[j+1] = a[j];
/* вставка */
a[j+1] = t;
}
}
8 8 8
| |
*
Обратная связь