bulgakov

38. Сортировка вставками и сложность алгоритмов

Сортировка вставками действует как игрок с картами: левая часть уже упорядочена, а очередную карту вставляют на нужное место. Это второй алгоритм из лекции. После него сравним оба метода по числу действий и узнаем, что означает запись O(n²). Основа та же: массив, цикл и пузырьковая сортировка.

Что пригодится из прошлого: массивы, цикл while, break, пузырьковая сортировка. Если эти темы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Идея метода

Представьте, что вы раскладываете карты в руке по порядку. Левой рукой вы держите уже упорядоченные карты. Правой берёте следующую карту из колоды и вставляете её между теми, что держите: сдвигаете большие карты вправо и кладёте новую на освободившееся место. Метод делает то же самое с числами массива.

Алгоритм:

  1. Берём элемент a[i] по очереди: i = 1, 2, …, n - 1.
  2. Вставляем 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 запишем массив. Полная программа печатает эту таблицу:

C
#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. Полная программа:

C
#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.

Сортировка вставками по убыванию
C
#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 (число занимает не меньше четырёх позиций, чтобы столбцы получились ровными). Главное здесь — итоговая таблица.

C
#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 сравнений.
ПрактикаЗагружаем тест…