2.1. Сортировка методом прямого включения
 

Пусть имеется последовательность элементов а₀, а₁, a₂, ..., а_n-1. Эта последовательность мысленно делится на две последовательности: упорядоченную последоваельность а₀, а₁, ....,a_i-1 и исходную, неупорядоченную a_i, a_i+1, ..., a_n-1. Очевидно, что первоначально упорядоченная последовательность состоит из единственного элемента а₀. При каждом шаге, начиная с i = 1 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент а_i, и вставляется в готовую последовательность в нужное место, при необходимости сдвигая элементы готовой последовательности на одну позицию вправо вплоть i-й позиции. Поиск подходящего места осуществляется сравнением а_i, с элементами a_j, j=i-1, i-2, ..., 0, и одновременным обменом местами а_i, и c_j, если а_i<a_j, т.е. сдвигом a_j на одну позицию вправо. Процесс поиска заканчивается при выполнении одного из условий:

• a_i≥а_j,
• достигнут левый конец готовой последовательности.

Для процедуры сортировки методом прямого включения число сравнений С и число пересылок М таковы: C_m,n = n-1; С_средн = (n2 + n - 2)/4; С_mах = (n2 - n)/2 - 1; M_min = 2(n - 1); М_средн= (n2+ 9n - 10)/4; М_mах = (n2 + Зn - 4)/2.

Рассмотрим пример программы сортировки методом прямого включения.
Пример.

/* СОРТИРОВКА МЕТОДОМ ПРЯМОГО ВКЛЮЧЕНИЯ */
#include
#define n 8
int A[n]={27,412,71,81,59,14,273,87};
main()
{ void Sis(int A[],int nn);
int j;
printf("\n Исходный массив: \n\t");
for (j=0; j<n; j++)
printf("%d\t",A[j]);
printf("\n");
Sis(A.n);
printf("\n Отсортированный массив :\n\f);
for (j=0; j<n; j++)
printf("%d\t",A[j]);
printf("\n");
getch(); return 0; }

/*ФУНКЦИЯ СОРТИРОВКИ ПРЯМЫМ ВКЛЮЧЕНИЕМ*/
void Sis(int A[],int nn)
{ int i,j,k;
printf("\n Отладочная печать по шагам сортировки");
for (i=1; i<nn; i++)
{k=A[i];
j=i-1;
while (k<A[j] && j >=0)
{ A[j+1]=A[j];
j--;}
/* Отладочная печать */
printf("\n i=%d",i);
for (j=0; j<nn; j++)
printf("\t%d",A[j]);
}
}

Исходный массив:
27  412   71   81   59   14   273   87
Отладочная печать по шагам сортировки:
i=1  27  412  71  81  59  14  273  87
i=2  27  71  412  81  59  14  273  87
i=3  27  71  81  412  59  14  273  87
i=4  27  59  71  81  412  14  273  87
i=5  14  27  59  71  81  412  273  87
i=6  14  27  59  71  81  273  412  87
i=7  14  27  59  71  81  87  273  412

Отсортированный массив:
14   27   59   71   81   87   273   412

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

Среднее число сравнений здесь С = O(nlog₂n), а среднее число сдвигов М = О(n₂).

Пример

/* СОРТИРОВКА МЕТОДОМ ПРЯМОГО ВКЛЮЧЕНИЯ С ДЕЛЕНИЕМ ПОПО-ЛАМ */
«include
define n 8

int A[n]={27,412,71,81,59,14,273,87};
main()
{ void BinIns(int A[],int nn);
int j;
printf("\n Исходный массив \n");
for (j=0; j<n; j++)
printf("\t%d",A[j]);
printf("\n");
BinIns(A,n);
printf("\n Отсортированный массив \n");
for (j=0; j<n; j++)
printf("\t%d",A[j]);
printf("\n");
getch(); return 0;
}
/* ФУНКЦИЯ СОРТИРОВКИ ПРЯМЫМ ВКЛЮЧЕНИЕМ С ДЕЛЕНИЕМ ПОПО-ЛАМ */
void Binlns(int A[],int nn)
{ int i,j,x,m,L,R;
printf("\ Отладочная печать по шагам сортировки ");
for (i=1; i<nn; i++)
{ x=A[i]; L=0; R=i; printf("\n %d",i);
while (L<R)
{ m=(L+R)/2;
if (A[m] ≤x)
L=m+1;
else
R=m;
}
for (j=i; j≥R; j--)
A[R]=x;
/* Отладочная печать по шагам сортировки */
for (j=0; j<nn;j++)
printf("\t %d”,A[j]);
}
}

Исходный массив 27   412   71   81   59   14   273   87
Отладочная печать по шагам сортировки:

j=1   27  412  71  81  59  14  273  87
j=2   27  71  412  81  59  14  273  87
j=3   27  71  81  412  59  14  273  87
j=4   27  59  71  81  412  14  273  87
j=5   14  27  59  71  81  412  273  87
j=6   14  27  59  71  81  273  412  87
j=7   14  27  59  71  81  87  273  412
Отсортированный массив:
14   27   59   71   81   87   273   412