Функция сортировки с помощью метода прямого включения

void insertionSort(int numbers[], int array_size)

{

int i, j , index;

for (i=l; i < array_size; i++)

{

index = numbers[i];

j = i;

while ((j > 0) && (numbers[j-1] > index))

{

numbers[j] = numbers[j-1];

j = j - i; }

numbers[j] = index; } }

Анализ алгоритма.Число сравнений ключей С_г при г-м просеивании составляет самое большое /-1, самое меньшее 1. Если предположить, что все перестановки из п ключей равновероятны, то среднее число сравнений — г/2. Число пересылок M_t равно С_г+2. Поэтому общее число сравнений и пересылок таковы [3]:

C_cp = {n² + n- 2)1 A; M_cp = (n²+9n-)/4; C_max = (n² + n- 4)/4; M_min = (n² + Ъп- 4)/2.

Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие же оценки — когда элементы первоначально расположены в обратном порядке.

Резюме: сортировка методом прямого включения — не очень подходящий метод для ЭВМ, так как включение элемента с последующим сдвигом на одну позицию целой группы элементов неэффективно.