Рассмотрим реализацию функций сортировки прямым включением и выбором на С++
/* ФУНКЦИЯ СОРТИРОВКИ ПРЯМЫМ ВКЛЮЧЕНИЕМ */
void Sis(int A[],int nn)
{ int i,j,k;
printf("\n Отладочная печать по шагам сортировки");
for ( j=1; j<nn; j++ )
{ k = A[j];
i = j -1;
while ( k < A[i] && i >= 0)
{ A[i+1] = A[i];
i -= 1; }
A[i+1] = k;
/* Отладочная печать */
printf("\n j = %d",j);
for (i=0; i<nn; i++)
printf("\t%d",A[i]);
}
}
Алгоритм с прямыми включениями можно легко улучшить с учетом того, что готовая последовательность, куда надо вставить новый элемент, уже упорядочена. Тогда место включения ищется методом двоичного (бинарного) поиска. Такой улучшенный алгоритм сортировки называется методом с двоичным включением (методом прямого включения с делением пополам). Однако применение этого алгоритма оправдано только тогда, когда число сортируемых элементов достаточно велико.
/* ФУНКЦИЯ СОРТИРОВКИ ПРЯМЫМ ВЫБОРОМ С ДЕЛЕНИЕМ ПОПОЛАМ */
void BinIns(int A[],int nn)
{ int i,j,x,m,L,R;
printf("\n Отладочная печать по шагам сортировки ");
for ( i=1; i<nn; i++ )
{ x = A[i]; L = 0; R = 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[j] = A[j-1];
A[R] = x;
/* отладочная печать */
printf("\ni=%d",i);
for (j=0; j<nn;j++)
printf("\t %d",A[j]);
}
}
/* ФУНКЦИЯ СОРТИРОВКИ ПРЯМЫМ ВЫБОРОМ */
void StrSel(int A[],int nn)
{ int i,j,x,k;
printf("\n Отладочная печать по шагам сортировки");
for ( i=0; i<nn-1; i++ )
{ x = A[i]; k = i;
for (j=i+1; j<nn; j++)
if (A[j] < x)
{ k = j; x = A[k]; }
A[k] = A[i]; A[i] = x;
printf("\n i=%d",i);
for (j=0; j<nn;j++)
printf("\t %d",A[j]);
}
}