Внутренняя сортировка данных методом простых вставок. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм

Сортировка вставками — простой алгоритм сортировки. Хотя этот алгоритм сортировки уступает в эффективности более сложным (таким как быстрая сортировка), у него есть ряд преимуществ:

§ эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;

§ эффективен на наборах данных, которые уже частично отсортированы;

§ это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);

§ может сортировать список по мере его получения;

§ использует O(1) временной памяти, включая стек.

Минусом же является высокая сложность алгоритма: O(n ²).

Принцип действия:

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

Пример

К 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703

i=1 503

i=2 087 503

i=3 087 503 512

i=4 061 087 503 512

И.т.д.

Фрагмент программы:

for (int i = 0; i < size - 1; ++i) {

/* устанавливаем начальное значение минимального индекса */

int min_i = i;

/* находим минимальный индекс элемента */

for (int j = i + 1; j < size; ++j) {

if (array[j] < array[min_i]) {

min_i = j;

}

}

/* меняем значения местами */

int temp = array[i];

array[i] = array[min_i];

array[min_i] = temp;

}