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

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

Элементы массива условно разделяются на готовую последовательность a1, a2, ..., ai-1 и входную последовательность ai, ai+1, ..., an. На каждом шаге i-й элемент помещается на подходящее место в готовую последовательность.

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

Реализация сортировки прямыми включениями
#include <stdio.h>
int main() {
  int a[10];
  int i, j, index;
  for(i=0;i<10;i++) {
    printf("a[%d] = ", i);
    scanf("%d",&a[i]);
  }
  for (i=1; i < 10; i++) {
    index = a[i];
    j = i;
    while ((j > 0) && (a[j-1] > index)) {
      a[j] = a[j-1];
      j = j - 1;
    }
    a[j] = index;
  }
  for(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.

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

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

Назад


Назад: Алгоритмы сортировки и поиска

Комментариев к записи: 1

  • Mission 9 Ball

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


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

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