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

Представьте себе колоду карт, из которой каждый раз вынимается и вставляется на указанное место одна карта. Такой способ упорядочения называется сортировкой методом вставок (insertion sort). В данном случае массив делится на две части: упорядоченную и неупорядоченную, как показано на рис.

Вначале весь массив неупорядочен. На каждом шаге метода вставок из неупорядоченной части извлекается первый элемент, который затем вставляется в нужное место упорядоченной части. Первый шаг тривиален: переместить нулевой элемент из неупорядоченной части в упорядоченную. Для этого даже не нужно переставлять элементы массива. Следовательно, этот шаг можно пропустить, считая, что этот элемент уже принадлежит упорядоченной части, а неупорядоченной частью массива является отрезок 1..N-1. Поскольку на каждом шаге размер упорядоченной части увеличивается на единицу, а размер неупорядоченной части, соответственно, на единицу уменьшается, в момент окончания алгоритма весь массив окажется упорядоченным.

На рис. показаны результаты сортировки массива, состоящего из пяти целых чисел, методом вставок. В исходном положении упорядоченная часть массива состоит из единственного нулевого элемента, равного 29, а к неупорядоченной части относятся все остальные элементы массива.

Извлечем из неупорядоченной части массива ее первый элемент - число 10 и вставим в соответствующее место упорядоченной части. Для этого понадобится сдвинуть элементы массива, чтобы освободить место для вставляемого числа. Снова извлечем из вновь образованной неупорядоченной части массива ее первый элемент - число 14 - и вставим в соответствующее место упорядоченной части и т.д.

int i,j,x;

for(i=1;i<n;i++)

{

x=a[i]; // запомнили элемент, который будем вставлять

j=i-1;

while(x<a[j]&&j>=0) // поиск подходящего места

{

a[j+1]=a[j]; // сдвиг вправо

j--;

}

a[j+1]=x; // вставка элемента

}

Не нашли, что искали? Воспользуйтесь поиском: