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

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

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

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

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

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

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

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

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

Реализация сортировки Шелла
void shellSort(int *num, int size) {
  int i, j, increment, temp;
  increment = 3;
  while (increment > 0) {
    for (i=0; i < size; i++) {
      j = i;
      temp = num[i];
      while((j>=increment) && (num[j-increment]>temp)) {
        num[j] = num[j - increment];
        j = j - increment;
      }
      num[j] = temp;
    }
    if (increment/2 != 0)
      increment = increment/2;
    else if (increment == 1)
      increment = 0;
    else
      increment = 1;
  }
}
Анализ алгоритма

Приводимая программа не ориентирована на некую определенную последовательность расстояний. Все 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 не будет опубликован. Обязательные поля помечены *