Interested Article - Сортировка Шелла

Сортировка Шелла на примере

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

Описание

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

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

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

История

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

Пример

Иллюстрация сортировки Шелла.

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

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

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

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

Выбор длины промежутков

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

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

Реализация на языках программирования

С++

template<typename RandomAccessIterator, typename Compare>
void shell_sort( RandomAccessIterator first, RandomAccessIterator last, Compare comp )
{
    for( auto d = ( last - first ) / 2; d != 0; d /= 2 )
    //нужен цикл для first = a[0..d-1]
        for( auto i = first + d; i != last; ++i )
            for( auto j = i; j - first >= d && comp( *j, *( j - d ) ); j -= d )
                std::swap( *j, *( j - d ) );
}

Си

void shell_sort(int *array, int size) {
    for (int s = size / 2; s > 0; s /= 2) {
        for (int i = s; i < size; ++i) {
            for (int j = i - s; j >= 0 && array[j] > array[j + s]; j -= s) {
                int temp = array[j];
                array[j] = array[j + s];
                array[j + s] = temp;
            }
        }
    }
}

Java

public class ShellSort {
    public static void shellSort(int[] array) {
        int h = 1;

        while (h <= array.length / 3) {
            h = h * 3 + 1;
        }

        while (h > 0) {
            for (int outer = h; outer < array.length; outer++) {
                int tmp = array[outer];
                int inner = outer;

                while (inner > h - 1 && array[inner - h] > tmp) {
                    array[inner] = array[inner - h];
                    inner -= h;
                }

                array[inner] = tmp;
            }

            h = (h - 1) / 3;
        }
    }
}

Python

def shell_sort(data: list[int]) -> list[int]:
    last_index = len(data)
    step = len(data)//2
    while step > 0:
        for i in range(step, last_index, 1):
            j = i
            delta = j - step
            while delta >= 0 and data[delta] > data[j]:
                data[delta], data[j] = data[j], data[delta]
                j = delta
                delta = j - step
        step //= 2
    return data

Примечания

  1. Shell D. L. (англ.) // Communications of the ACM — New York City: Association for Computing Machinery , 1959. — Vol. 2, Iss. 7. — P. 30—32. — ISSN ; —
  2. J. Incerpi, R. Sedgewick , «Improved Upper Bounds for Shellsort», J. Computer and System Sciences 31, 2, 1985.
  3. . Дата обращения: 15 сентября 2009. 30 августа 2011 года.

Ссылки

  • Дональд Кнут . Искусство программирования. Том 3. Сортировка и поиск, 2-е изд. Гл. 5.2.1. ISBN 5-8459-0082-4
Источник —

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