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

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

 

В 1959 г. Д. Шеллом было предложено усовершенствование сортировки с помощью прямого включения.

Сначала отдельно группируются и сортируются элементы, отстоящие друг от друга на 4 позиции. Такой процесс называется четвертной сортировкой.

После первого прохода элементы перегруппировываются — теперь каждый элемент группы отстоит от другого на 2 позиции — и вновь сортируются (двойная сортировка).

На третьем проходе идет обычная сортировка.
сортировка Шелла

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

Такой метод в результате дает упорядоченный массив, и каждый проход от предыдущих только выигрывает (так как каждая i-сортировка объединяет две группы, уже отсортированные 2i-сортировкой).

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

Реализация сортировки Шелла на Си

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
37
38
39
40
41
42
43
#define _CRT_SECURE_NO_WARNINGS // для корректной работы scanf()
#include <stdio.h>
// Функция сортировки Шелла
void shellSort(int *num, int size)
{
  int increment = 3;    // начальное приращение сортировки
  while (increment > 0)  // пока существует приращение
  {
    for (int i = 0; i < size; i++)  // для всех элементов массива
    {
      int j = i;          // сохраняем индекс и элемент
      int temp = num[i];
      // просматриваем остальные элементы массива, отстоящие от j-ого
      // на величину приращения
      while ((j >= increment) && (num[j - increment] > temp))
      {  // пока отстоящий элемент больше текущего
        num[j] = num[j - increment]; // перемещаем его на текущую позицию
        j = j - increment;       // переходим к следующему отстоящему элементу
      }
      num[j] = temp; // на выявленное место помещаем сохранённый элемент
    }
    if (increment > 1)      // делим приращение на 2
      increment = increment / 2;
    else if (increment == 1)   // последний проход завершён,
      break;  // выходим из цикла
  }
}
int main()
{
  int m[10];
  // Вводим элементы массива
  for (int i = 0; i<10; i++) 
  {
    printf("m[%d]=", i);
    scanf("%d", &m[i]);
  }
  shellSort(m, 10); // вызываем функцию сортировки
  // Выводим отсортированные элементы массива
  for (int i = 0; i<10; i++)
    printf("%.2d ", m[i]);
  getchar(); getchar();
  return 0;
}

Результат выполнения
Сортировка Шелла: результат

Анализ алгоритма

Приводимая программа не ориентирована на некую определенную последовательность расстояний. Все t расстояний обозначаются соответственно

h1, h2, ..., ht ,

для них выполняются условия

ht=1;

hi+1<hi.

Каждая h-сортировка программируется как сортировка с помощью прямого включения.

В алгоритме не известно, какие расстояния дают наилучшие результаты.

Дональд Кнут рекомендует такую последовательность:

1, 3, 7, 15, 31, ...,

то есть

hk-1=2hk+1,

ht=1 и  t = [log2n] - 1.


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

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

  • Лучшая последовательность установлена эмпирически Marcin Ciura: 1, 4, 10, 23, 57, 132, 301, 701, 1750, далее умножать на 2.25 и округлять вниз.


  • Валерия
    if (increment/2 != 0)

    В этой строчке точно нужно делить, просто мне показалось, что здесь нужен остаток от деления.


    • Да, там действительно приращение делится на 2 для каждого прохода.

      if (increment/2 != 0) // increment > 2
            increment = increment/2;
      else if (increment == 1) // increment = 1
            increment = 0;
      else                       // increment = 2
            increment = 1;

      В случае если частное от деления на 2 равно 0, мы имеем 0, 1 или 2.
      При increment = 2 получаем increment = 1
      При increment = 1 получаем increment = 0
      При increment = 0 выходим из цикла while


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

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