38. Сортировка вставками и сложность алгоритмов
Сортировка вставками действует как игрок с картами: левая часть уже упорядочена, а очередную карту вставляют на нужное место. Это второй алгоритм из лекции. После него сравним оба метода по числу действий и узнаем, что означает запись O(n²). Основа та же: массив, цикл и пузырьковая сортировка.
Что пригодится из прошлого: массивы, цикл while, break, пузырьковая сортировка. Если эти темы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Идея метода
Представьте, что вы раскладываете карты в руке по порядку. Левой рукой вы держите уже упорядоченные карты. Правой берёте следующую карту из колоды и вставляете её между теми, что держите: сдвигаете большие карты вправо и кладёте новую на освободившееся место. Метод делает то же самое с числами массива.
Алгоритм:
- Берём элемент
a[i]по очереди:i = 1, 2, …, n - 1. - Вставляем
a[i]в левую частьa[0] … a[i - 1]так, чтобы элементыa[0] … a[i]остались отсортированными.
С i = 0 не начинаем: массив из одного элемента a[0] уже отсортирован. Левая часть сначала состоит из одного элемента и растёт на единицу на каждом шаге. Когда i дойдёт до n - 1 и элемент будет вставлен, отсортирован весь массив.
Пример на восьми числах
Возьмём массив 4 3 2 10 12 1 5 6. Выполним метод и после каждого i запишем массив. Полная программа печатает эту таблицу:
#include <stdio.h>
int main(void)
{
int size = 8;
int arr[] = {4, 3, 2, 10, 12, 1, 5, 6};
for (int i = 1; i < size; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
printf("i = %d, key = %2d:", i, key);
for (int k = 0; k < size; k++) {
printf(" %2d", arr[k]);
}
printf("\n");
}
return 0;
}
Вывод:
i = 1, key = 3: 3 4 2 10 12 1 5 6
i = 2, key = 2: 2 3 4 10 12 1 5 6
i = 3, key = 10: 2 3 4 10 12 1 5 6
i = 4, key = 12: 2 3 4 10 12 1 5 6
i = 5, key = 1: 1 2 3 4 10 12 5 6
i = 6, key = 5: 1 2 3 4 5 10 12 6
i = 7, key = 6: 1 2 3 4 5 6 10 12
Разберём несколько строк.
i = 1, вставляем3. Левая часть —4. Число4больше трёх, оно сдвигается вправо, а тройка встаёт на первое место:3 4. Это первая строка таблицы: отсортированная часть пока состоит из одногоa[0] = 4, и в неё вставляетсяa[1] = 3.i = 2, вставляем2. Левая часть3 4. Оба числа больше двойки, оба сдвигаются, двойка встаёт в начало:2 3 4.i = 3, вставляем10. Левая часть2 3 4. Наибольшее из неё,4, не больше десяти, поэтому сдвигать нечего. Десятка остаётся на месте. То же приi = 4для12.i = 5, вставляем1. Это самый тяжёлый шаг: единица меньше всех пяти чисел слева. Все пять сдвигаются вправо, единица встаёт в начало.i = 7, вставляем6. Слева1 2 3 4 5 10 12. Сдвигаются только10и12, шестёрка встаёт после пятёрки.
Самый наглядный шаг — i = 5. Вынимаем единицу, освобождая место, и по очереди двигаем соседей слева вправо. Знак _ — свободная ячейка:
вынули key = 1: 2 3 4 10 12 _ 5 6
сдвиг 12 вправо: 2 3 4 10 _ 12 5 6
сдвиг 10 вправо: 2 3 4 _ 10 12 5 6
сдвиг 4 вправо: 2 3 _ 4 10 12 5 6
сдвиг 3 вправо: 2 _ 3 4 10 12 5 6
сдвиг 2 вправо: _ 2 3 4 10 12 5 6
вставили key: 1 2 3 4 10 12 5 6
Видно главное: чем дальше элемент должен уйти влево, тем больше сдвигов.
Программа
Отсортируем по возрастанию массив 14 33 27 10 35 19 42 44. Полная программа:
#include <stdio.h>
int main(void)
{
int size = 8;
int arr[] = {14, 33, 27, 10, 35, 19, 42, 44};
int i, key, j;
for (i = 1; i < size; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
for (int k = 0; k < size; k++) {
printf("%d ", arr[k]);
}
printf("\n");
return 0;
}
Вывод:
10 14 19 27 33 35 42 44
Разберём внутренний цикл, это сердце алгоритма.
key = arr[i];— запоминаем вставляемый элемент. Это нужно, потому что его местоarr[i]скоро будет затёрто сдвигом.j = i - 1;—jидёт по левой части справа налево, начиная с её последнего элемента.while (j >= 0 && arr[j] > key)— пока слева есть элементы и текущий большеkey, сдвигаем:arr[j + 1] = arr[j];, затемj = j - 1;.arr[j + 1] = key;— когда цикл остановился,j + 1— место дляkey: слева от него всё не больше, справа всё больше.
Порядок частей в условии j >= 0 && arr[j] > key важен. Оператор && вычисляет правую часть, только если левая истинна. Когда j стал -1, проверка j >= 0 ложна, и arr[-1] не читается. Если поменять части местами, программа прочитает память перед началом массива.
Чтобы получить сортировку по убыванию, меняют знак: arr[j] < key.
Сортировка вставками по убыванию
#include <stdio.h>
int main(void)
{
int size = 8;
int arr[] = {14, 33, 27, 10, 35, 19, 42, 44};
for (int i = 1; i < size; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] < key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
for (int k = 0; k < size; k++) {
printf("%d ", arr[k]);
}
printf("\n");
return 0;
}
Вывод: 44 42 35 33 27 19 14 10.
Левая часть теперь должна быть упорядочена по убыванию. Сдвигаем элементы, которые меньше key, и вставляем key перед ними. Всё остальное не меняется.
Сколько работы делают алгоритмы
Оба метода справляются, но сколько действий они выполняют? Измерим на счётчиках. Программа сортирует массивы разной длины тремя способами и считает сравнения элементов. Это простая версия пузырька, версия с границей compareUntil и вставки. Массивы двух видов: уже отсортированный и «наоборот» (самый неудобный порядок). Функции повторяют алгоритмы и добавляют comparisons++ при каждом сравнении. Во вставках внутренний цикл записан через break (урок про break), чтобы сосчитать и последнее сравнение, после которого сдвиг прекращается.
В этой программе три новых мелочи: массив sizes с тремя длинами, повторное заполнение массива перед каждым запуском и формат %4d (число занимает не меньше четырёх позиций, чтобы столбцы получились ровными). Главное здесь — итоговая таблица.
#include <stdio.h>
int count_bubble(int arr[], int size)
{
int comparisons = 0;
int swapped;
do {
swapped = 0;
for (int i = 0; i < size - 1; i++) {
comparisons++;
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = 1;
}
}
} while (swapped);
return comparisons;
}
int count_bubble_shrink(int arr[], int size)
{
int comparisons = 0;
int compareUntil = size;
int swapped;
do {
swapped = 0;
for (int i = 0; i < compareUntil - 1; i++) {
comparisons++;
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = 1;
}
}
compareUntil--;
} while (swapped);
return comparisons;
}
int count_insertion(int arr[], int size)
{
int comparisons = 0;
for (int i = 1; i < size; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0) {
comparisons++;
if (arr[j] <= key) {
break;
}
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return comparisons;
}
void fill_reversed(int arr[], int size)
{
for (int i = 0; i < size; i++) {
arr[i] = size - i;
}
}
void fill_sorted(int arr[], int size)
{
for (int i = 0; i < size; i++) {
arr[i] = i + 1;
}
}
int main(void)
{
int sizes[] = {10, 20, 40};
int arr[40];
printf(" n order bubble shrinking insertion\n");
for (int k = 0; k < 3; k++) {
int n = sizes[k];
fill_reversed(arr, n);
int a = count_bubble(arr, n);
fill_reversed(arr, n);
int b = count_bubble_shrink(arr, n);
fill_reversed(arr, n);
int c = count_insertion(arr, n);
printf("%4d reversed %7d %10d %10d\n", n, a, b, c);
fill_sorted(arr, n);
a = count_bubble(arr, n);
fill_sorted(arr, n);
b = count_bubble_shrink(arr, n);
fill_sorted(arr, n);
c = count_insertion(arr, n);
printf("%4d sorted %7d %10d %10d\n", n, a, b, c);
}
return 0;
}
Вывод:
n order bubble shrinking insertion
10 reversed 90 45 45
10 sorted 9 9 9
20 reversed 380 190 190
20 sorted 19 19 19
40 reversed 1560 780 780
40 sorted 39 39 39
Картинкой (один блок ▇ — примерно 40 сравнений, массив «наоборот»):
n = 10 вставки и версия с границей 45 ▇
простой пузырёк 90 ▇▇
n = 20 вставки и версия с границей 190 ▇▇▇▇▇
простой пузырёк 380 ▇▇▇▇▇▇▇▇▇▇
n = 40 вставки и версия с границей 780 ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
простой пузырёк 1560 ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
Что видно.
- Худший случай (массив «наоборот»). Простой пузырёк делает
n · (n - 1)сравнений:10 · 9 = 90,20 · 19 = 380,40 · 39 = 1560. Вариант с границей и вставки делают вдвое меньше,n · (n - 1) / 2:45,190,780. Сумма(n - 1) + (n - 2) + … + 1и даёт эту формулу. Её легко увидеть на картинке дляn = 6: проходы выкладываются лесенкой, а лесенка — это половина прямоугольника6 × 5:
проход 1: ■ ■ ■ ■ ■ 5 сравнений
проход 2: ■ ■ ■ ■ 4
проход 3: ■ ■ ■ 3
проход 4: ■ ■ 2
проход 5: ■ 1
всего 5 + 4 + 3 + 2 + 1 = 15 = 6 · 5 / 2
- Рост. Длина выросла вдвое, а число сравнений примерно вчетверо:
45 → 190 → 780. - Лучший случай (массив уже отсортирован). Всем трём методам хватает
n - 1сравнений. У пузырька это один проход без замен, у вставок — по одному сравнению на каждый элемент, начиная со второго.
Что означает O(n²)
Для обоих алгоритмов говорят: сложность O(n²) (читается «о от эн квадрат»). Это способ сказать, как растёт число действий вместе с размером данных n, без точных множителей. Когда n удваивается, работа примерно учетверяется, как в таблице выше. Для n = 1000 по формуле n · (n - 1) / 2 получается 499 500 сравнений. Для n = 100 000 — уже 4 999 950 000, почти пять миллиардов. Поэтому такие методы подходят для небольших массивов и для учёбы.
Запись O(n²) — это оценка роста числа действий. Мы оцениваем худший случай, то есть самый неудобный порядок данных. На уже отсортированном массиве проходов меньше, как показано выше. В реальных программах для больших массивов используют готовые быстрые алгоритмы из стандартной библиотеки, но понять их проще после этих двух.
Видео с анимацией этого метода (на английском) — Insertion Sort - Animation Video.
Что запомнить
- Сортировка вставками: левая часть упорядочена; очередной элемент вставляется на своё место сдвигом больших элементов вправо.
keyхранит вставляемое значение; условиеj >= 0 && arr[j] > keyпроверяет границу раньше, чем обращается к элементу.- Пузырьковая сортировка и вставки имеют сложность
O(n²): при удвоенииnчисло сравнений примерно учетверяется. - На уже упорядоченных данных оба метода работают за
n - 1сравнений.
