Элементы массива условно разделяются на готовую последовательность
{\displaystyle{a_1, a_2, \ldots a_{i-1}}}
и входную последовательность
{\displaystyle{a_i, a_{i+1}, \ldots a_n}}
На каждом шаге {\displaystyle{i}}-й элемент помещается на подходящее место в готовую последовательность.
Для этого движемся от рассматриваемого элемента в сторону начала готовой последовательности и смещаем вправо на 1 элемент все элементы готовой последовательности, которые больше рассматриваемого.
В результате рассматриваемый элемент помещается в готовую последовательность между элементами, меньшими его, и элементами, большими его.
Реализация сортировки прямыми включениями на Си
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
35
36
#define _CRT_SECURE_NO_WARNINGS // для корректной работы scanf()
#include <stdio.h>
#define SIZE 10 // размер массива сортируемых элементов
// Функция сортировки прямыми включениями
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[SIZE]; // Объявляем массив из 10 элементов
// Вводим значения элементов массива
for (int i = 0; i < SIZE; i++)
{
printf("a[%d] = ", i);
scanf("%d", &a[i]);
}
inclusionSort(a, SIZE); // вызываем функцию сортировки
// Выводим отсортированные элементы массива
for (int i = 0; i < SIZE; i++)
printf("%d ", a[i]);
getchar();
getchar();
return 0;
}Результат выполнения
Анализ выполнения
Число сравнений ключей {\displaystyle{C_i}} при {\displaystyle{i}}-м просеивании составляет самое большое {\displaystyle{i-1}} , самое меньшее – 1.
Если предположить, что все перестановки из n ключей равновероятны, то среднее число сравнений – {\displaystyle{\frac {i}{2}}}.
Поэтому общее число сравнений {\displaystyle{C_i}} и перестановок {\displaystyle{M_i}} таково:
{\displaystyle{C_{min}=n-1 \ \ M_{min}=2\cdot(n-1)}}
{\displaystyle{C_{max}=\frac{n \cdot (n-1)}{2} \ \ M_{max}=\frac{n + 3 \cdot n — 4}{2}}}
Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие оценки — когда элементы первоначально расположены в обратном порядке.Резюме: сортировка методом прямого включения – не очень подходящий метод для компьютера, поскольку включение элемента с последующим сдвигом на одну позицию целой группы элементов неэффективно.
