Сортировка Шелла

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Сортировка Шелла
Пошаговая визуализация сортировки Шелла
Сортировка с шагами 23, 10, 4, 1.
Предназначение

Алгоритм сортировки

Структура данных

Массив

Худшее время

зависит от выбранных шагов

Лучшее время

O(n*k) сравнений,
O(k) обменов,
где k - количество шагов

Среднее время

зависит от выбранных шагов

Затраты памяти

О(n) всего, O(1) дополнительно

Процесс перестановки элементов в сортировке Шелла

Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Дональда Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга; иными словами — это сортировка вставками, но с предварительными «грубыми» проходами.

Аналогичный метод усовершенствования «пузырьковой» сортировки называется «сортировка расчёской».

Описание[править | править вики-текст]

Пусть имеется некий абстрактный массив данных «», множество составных элементов которого (обозначаемых как , где — любое целое число из интервала [0; N−1]) требуется упорядочить методом Дональда Шелла. Упорядочение будет производиться в рамках последовательно выбираемых пар вида , где , причём целые числа.

Этапы алгоритма:

  1. Инициализация: задание начального значения — которое впоследствии будет уменьшаться (о выборе значения см. ниже);
  2. Основная часть:
    1. Упорядочение массива:
      1. Выбор пары элементов, индексы которых отличаются на ;
      2. Определение разности элементов выбранной пары;
      3. Упорядочение элементов в рамках пары согласно разности значений;
      4. Переход к следующей паре;
    2. Уменьшение значения ;
    3. Проверка: если — вернуться к пункту "1" основной части (и если — для проведения обычной сортировки вставками);
  3. Завершение работы (например, вывод результатов на экран).

Эффективность сортировки Шелла, — в определённых случаях, — обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, — например, пузырьковой, — каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла — это число может быть больше).

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка — она имеет ряд преимуществ:

  • Отсутствие потребности в памяти под стек;
  • Отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла.

История[править | править вики-текст]

Сортировка Шелла была названа в честь её изобретателя — Дональда Шелла, который опубликовал этот алгоритм в 1959 году.

Пример[править | править вики-текст]

Shellsort-ru.svg


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

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

В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов.

Процесс завершается обычной сортировкой вставками получившегося списка.

Выбор длины промежутков[править | править вики-текст]

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

  • первоначально используемая Шеллом последовательность длин промежутков: в худшем случае, сложность алгоритма составит ;
  • предложенная Хиббардом (англ.) последовательность: все значения ; такая последовательность шагов приводит к алгоритму сложностью ;
  • предложенная Седжвиком последовательность: , если i чётное и , если i нечётное. При использовании таких приращений средняя сложность алгоритма составляет: , а в худшем случае порядка . При использовании формулы Седжвика следует остановиться на значении inc[s-1], если 3*inc[s] > size[1];
  • предложенная Праттом (англ.) последовательность: все значения ; в таком случае сложность алгоритма составляет ;
  • эмпирическая последовательность Марцина Циура (последовательность A102549 в OEIS): ; является одной из лучших для сортировки массива ёмкостью приблизительно до 4000 элементов[2];
  • эмпирическая последовательность, основанная на числах Фибоначчи: ;
  • все значения [источник не указан 2428 дней], ; такая последовательность шагов приводит к алгоритму сложностью .

Реализация на C[править | править вики-текст]

// BaseType - любой перечисляемый тип 
// typedef int BaseType - пример
void ShellsSort(BaseType *A, unsigned N)
{
	BaseType t;
	for(unsigned k = N/2; k > 0; k /= 2)
        for(unsigned i = k; i < N; i += 1)
        {
            t = A[i];
            unsigned j;
            for(j = i; j >= k; j -= k)
            {
                if(t < A[j-k])
                    A[j] = A[j-k];
                else
                    break;
            }
            A[j] = t;
        }
}

Примечания[править | править вики-текст]

  1. J. Incerpi, R. Sedgewick, «Improved Upper Bounds for Shellsort», J. Computer and System Sciences 31, 2, 1985.
  2. Marcin Ciura Best Increments for the Average Case of Shellsort

Ссылки[править | править вики-текст]