Основы программирования на С++ для начинающих

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

Еще одним алгоритмом, разработанным для упорядочивания массивов, является алгоритм Сортировка вставками (Insertion Sort). Этот алгоритм (как и другие, рассматриваемые на нашем сайте) достаточно прост. Он состоит из двух циклов (один вложен в другой). Первый цикл производит проход по массиву, а второй – перемещение обрабатываемых элементов. Давайте сразу посмотрим, как может выглядеть код такой сортировки, а уже ниже разберем, как он работает.

Алгоритм Сортировка вставками можно описать следующими позициями:

  1. Запомнить во временную переменную ( buff в примере) значение текущего элемента массива;
  2. Пока элементы слева от запомненного значения больше чем запомненное – перемещаем их на позицию вправо. Получается, что предыдущий элемент займет ячейку запомненного. А тот, что стоит перед предыдущим – переместится в свою очередь на место предыдущего. И так  элементы будут двигаться друг за дружкой.
  3. Движение элементов заканчивается, если очередной элемент, который нужно сдвинуть, оказывается по значению меньше, чем тот, что запомнили во временную переменную в начале цикла.
  4. Цикл берет следующий элемент, и опять сдвигает все, которые расположены перед ним и большие по значению.

Покажем визуально перемещение значения в массиве из семи элементов во время работы Сортировки вставками:

сортировка вставками с++, алгоритм сортировки вставками, программирование для начинающих

На первой итерации в переменную-буфер запишется   значение из ячейки с индексом 1 и цикл будет проверять этот элемент. Там у нас находится число 2. Оно больше значения, которое записано в нулевой ячейке, поэтому перемещений не будет. Далее в переменную-буфер запишется значение из ячейки с индексом 2 и снова пойдет сравнение со значениями слева и т.д.  Только на четвертой итерации внешнего цикла начнется перезапись значений. Тройка сначала поменяется местами с пятеркой, а затем с четверкой.

Таким образом, в процессе Сортировки вставками  элемент записанный в buff “просеивается” к началу массива. А  в случаях, когда будет найден элемент со значением меньше чем buff или будет достигнуто начало последовательности – просеивание останавливается.

Хорошая визуальная иллюстрация алгоритма Сортировка вставками есть на википедии:

сортировка вставками с++, алгоритм сортировки вставками, программирование для начинающих

Затраты времени на работу данного алгоритма полностью зависят от начальных данных: количества элементов в массиве и его изначальной упорядоченности. Это понятно, что чем больше массив – тем больше времени надо на его обработку. Также больше времени потребуется на сортировку  массива в котором значения абсолютно не упорядочены.

Алгоритм Сортировка вставками хорош для небольших массивов (до нескольких десятков элементов). Еще эффективнее работает, если данные такого массива ранее были частично отсортированы. Если в массив будут добавляться новые данные (новые элементы), алгоритм сможет их сортировать по мере их добавления (в отличии от сортировки пузырьком и сортировки выбором). Эффективность алгоритма значительно возрастет, если добавить в код алгоритм бинарного поиска.

Предлагаем также посмотреть короткий видоурок по информатике с разбором алгоритма Сортировка вставками:

6 thoughts on “Сортировка вставками

    1. А зачем? В этой сортировке это и так легко посчитать – общее число 2-х циклов = N * (N-1) / 2 … и не нужно ничего выводить.

      Но вычислительную сложность сортировок (любых) меряют не какими-то повторениями циклов, а оценивают степенью роста числа операций сравнений и перестановок от длины N. И это заранее известно, что плохие сортировки (пузырьковая, вставками … и почти все другие) имеют степень сложности O(N)=N*N (квадратичную), а хорошие (быстрые рекурсивные) – O(N)=N*log(N).

    1. В таком случае оно их не изменяет, а в конце выведет что-то вроде 12 12 12 12 12 24 45 45 96 96

  1. Всё, понял, почему оно работает.
    for (j = i – 1; j >= 0 && a[j] > buff; j–) a[j + 1] = a[j];
    a[j + 1] = buff; // и поставим запомненный на его новое место
    }

    Вот так понятно, а то кажется, что
    for (j = i – 1; j >= 0 && a[j] > buff; j–)
    {
    a[j + 1] = a[j];
    a[j + 1] = buff; // и поставим запомненный на его новое место
    }

Добавить комментарий для Maniacal Отменить ответ

Ваш e-mail не будет опубликован. Обязательные поля помечены *