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

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

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

Сортировка вставками C++C++ #include <iostream> using namespace std; int main() { const int N = 10; int a[N] = { 12, 5, 3, 2, 45, 96, 6, 8, 11, 24 }; int buff = 0; // для хранения перемещаемого значения int i, j; // для циклов /************* Начало сортировки *******************/ for (i = 1; i < N; i++) { buff = a[i]; // запомним обрабатываемый элемент // и начнем перемещение элементов слева от него // пока запомненный не окажется меньше чем перемещаемый for (j = i - 1; j >= 0 && a[j] > buff; j--) a[j + 1] = a[j]; a[j + 1] = buff; // и поставим запомненный на его новое место } /************* Конец сортировки *******************/ for (int i = 0; i < N; i++) // вывод отсортированного массива cout << a[i] << '\t'; cout << endl; }12345678910111213141516171819202122232425262728#include <iostream>using namespace std; int main(){ const int N = 10; int a[N] = { 12, 5, 3, 2, 45, 96, 6, 8, 11, 24 };  int buff = 0; // для хранения перемещаемого значения int i, j; // для циклов   /************* Начало сортировки *******************/ for (i = 1; i < N; i++) { buff = a[i]; // запомним обрабатываемый элемент // и начнем перемещение элементов слева от него // пока запомненный не окажется меньше чем перемещаемый for (j = i - 1; j >= 0 && a[j] > buff; j--) a[j + 1] = a[j];   a[j + 1] = buff; // и поставим запомненный на его новое место } /************* Конец сортировки *******************/  for (int i = 0; i < N; i++) // вывод отсортированного массива cout << a[i] << '\t'; cout << endl;}

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

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

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

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

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

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

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

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

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

4.312
📎📎📎📎📎📎📎📎📎📎