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

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

 

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









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

a1, a2, …, ai-1

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

ai, ai+1, …, an.

На каждом шаге 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
#define _CRT_SECURE_NO_WARNINGS // для корректной работы scanf()
#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



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

Добавить комментарий

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