Вы здесь

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

Исходный код на C++: 

Теория

Сортировка вставками предполагает наличие отсортированной части массива, в которую добавляется новый элемент, с учётом порядка следования элементов. На каждом шаге работы алгоритма берем i-ый элемент массива и сравниваем его с каждым элементом в упорядоченной части массива, находим элемент больше i. Далее сдвигаем часть элементов вправо, освобождая место для вставки нового элемента, и вставляем i-ый элемент. Приведём пример. Дан входной массив чисел: 66,74,-15,89,13,85,-77,16. На первом шаге сортировки вставками сравниваем i-ый( i=1) с j-ым(j=0) данную пару оставляем без изменений. После первого шага получим (рис. 1).

После первого шага работы алгоритма
Рис 1. Сортировка вставками Шаг 1.

На втором шаге сортировки сравниваем i-ый(i=2) элемент с каждым j-ым(j=0,1) элемент. Находим первый элемент больше i, упорядоченную последовательность сдвигаем вправо и вставляем i-ый элемент на нулевую позицию. Таким образом, после второго шага получим (рис. 2).

После второго шага работы алгоритма
Рис 2. Сортировка вставками Шаг 2.

На третьем шаге работы алгоритма сравниваем i-ый(i=3) элемент с каждым j-ым(j=0,1,2) элементом. Данная последовательность является упорядоченной, поэтому на данном шаге массив имеет следующий вид -15,66,74,89,13,85,-77,16. На четвёртом шаге сортировки сравниваем i-ый (i=4) элемент с каждым j-ым (j=0,1,2,3) элементом, так как -15<13<66, вставляем 13 на 1 позицию. Массив имеет следующий вид -15,13,66,74,89,85,-77,16.Продолжая итерационный процесс, мы получим отсортированный массив. Трудоёмкость алгоритма- n*n/4.

Программная реализация

void sort_vstavka(int count,double *mass)
{
int i,j,p;
double min;
for(i=1;i&lt;count;i++)
{
min=mass[i];
for(j=0;j&lt;i;j++)
if(mass[j]&gt;min) break;
for(p=i-1;p&gt;=j;p--)
mass[p+1]=mass[p];
mass[j]=min;
}
}