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

Пусть задан массив Предполагая, что элементы удовлетворяют неравенствам

будем сравнивать элемент x i с элементами Как только он окажется не меньше, чем x j , поставим его на место j +1 , предварительно сдвинув элементы на одну позицию вправо. Эти операции выполняются с помощью цикла

t = x [ i ]; // i >0

for (j=i-1; j>=0 && t<x[j]; j--)

x [ j +1]= x [ j ]; //сдвиг на одну позицию

x [ j +1]= t ;

Поскольку массив, состоящий из единственного элемента x [0] , отсортирован, то выполняя эти операции для получим отсортированный массив

Приведем подпрограмму сортировки массива методом простых вставок и тестовую программу:

#include <stdlib.h>

#include <stdio.h>

#include <time.h>

void insert (int *x, int n) //сортировка вставками

{ int i, j, t;

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

{ t=x[i];

for (j=i-1; j>=0 && t<x[j]; j--)

x [ j +1]= x [ j ]; //сдвиг на одну позицию

x[j+1]=t;

}

}

main()

{ int a[10]; int i;

randomize (); //случайный выбор первого числа

for ( i =0; i <10; i ++)

a [ i ]= random (200); //случайное число 0-199

printf(" До сортировки :\n");

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

printf (" %3 d ", a [ i ]);

insert ( a , 10); //вызов подпрограммы сортировки

printf("\n После сортировки :\n");

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

printf (" %3 d ", a [ i ]);

}

Результат работы программы

До сортировки:

135 88 171 135 198 187 34 41 173

После сортировки:

41 88 135 135 171 173 185 187 198

Число сравнений t  <  x [ j ] в наихудшем случае равно Если массив упорядочен, то подпрограмма не будет переставлять элементы. В этом смысле алгоритм ведет себя естественно. Число операций копирования t = x [ i ], x [ j +1]= x [ j ] и x [ j +1]= t равно колич 179 еству сравнений. Поскольку каждая транспозиция (перестановка двух элементов) состоит из двух копирований, то данная подпрограмма содержит транспозиций.