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

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-\0)/4; C_max = (n² + n- 4)/4; M_min = (n² + Ъп- 4)/2.

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

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

Сортировка с помощью прямого выбора

Метод сортировки основан на следующих правилах [1, 3, 9, 10, 13]:

1. Выбирается элемент с наименьшим ключом.

2. Он меняется местами с первым элементом а₀.

3. Затем эти операции повторяются с оставшимися п-\ элементами, п-2 элементами и так далее до тех пор, пока не останется один, самый большой элемент.

На рис. 3.3 приведен процесс сортировки этим методом.