Сортировка прямыми включениями

Сортировка прямыми включениями

Рассмотрим алгоритм сортировки прямыми включениями.

Элементы массива условно разделяются на готовую последовательность

{\displaystyle{a_1, a_2, \ldots a_{i-1}}}

и входную последовательность

{\displaystyle{a_i, a_{i+1}, \ldots a_n}}

На каждом шаге {\displaystyle{i}}-й элемент помещается на подходящее место в готовую последовательность.

Для этого движемся от рассматриваемого элемента в сторону начала готовой последовательности и смещаем вправо на 1 элемент все элементы готовой последовательности, которые больше рассматриваемого.

В результате рассматриваемый элемент помещается в готовую последовательность между элементами, меньшими его, и элементами, большими его.

Сортировка прямыми включениями

Реализация сортировки прямыми включениями на Си

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}}}

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

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

3 комментария к “Сортировка прямыми включениями”

  1. Mission 9 Ball

    Улучшенные методы сортировки основываются на тех же принципах, что и прямые, но используют некоторые оригинальные идеи для ускорения процесса

Оставьте комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Прокрутить вверх