Рассмотрим алгоритм сортировки прямыми включениями.
Элементы массива условно разделяются на готовую последовательность
a1, a2, …, ai-1
и входную последовательность
ai, ai+1, …, an.
На каждом шаге i-й элемент помещается на подходящее место в готовую последовательность.
Реализация сортировки прямыми включениями на Си
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
// Функция сортировки прямыми включениями
void inclusionSort(int *num, int size)
{
// Для всех элементов кроме начального
for (int i = 1; i < size; i++)
{
int value = num[i]; // запоминаем значение элемента
int index = i; // и его индекс
while ((index > 0) && (num[index - 1] > value))
{ // смещаем другие элементы к концу массива пока они меньше index
num[index] = num[index - 1];
index--; // смещаем просмотр к началу массива
}
num[index] = value; // рассматриваемый элемент помещаем на освободившееся место
}
}
int main()
{
int a[10]; // Объявляем массив из 10 элементов
// Вводим значения элементов массива
for (int i = 0; i < 10; i++)
{
printf("a[%d] = ", i);
scanf("%d", &a[i]);
}
inclusionSort(a, 10); // вызываем функцию сортировки
// Выводим отсортированные элементы массива
for (int i = 0; i<10; i++)
printf("%d ", a[i]);
getchar(); getchar();
return 0;
}
Результат выполнения
Анализ выполнения
Число сравнений ключей Ci при i-м просеивании составляет самое большое i-1, самое меньшее – 1. Если предположить, что все перестановки из n ключей равновероятны, то среднее число сравнений – i/2. Число пересылок
Mi = Ci+2.
Поэтому общее число сравнений и пересылок таковы:
Cmin=n-1; Mmin=3(n-1);
Cср=(n2+n-2)/4; Mср=(n2+9n-10)/4;
Cmax=(n2+n-4)/4; Mmax=(n2+3n-4)/2.
Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие оценки — когда элементы первоначально расположены в обратном порядке.
Резюме: сортировка методом прямого включения – не очень подходящий метод для компьютера, поскольку включение элемента с последующим сдвигом на одну позицию целой группы элементов неэффективно.
Назад: Алгоритмы сортировки и поиска
Комментариев к записи: 3