Алгоритм сортировки Шелла с примером

Что такое сортировка Шелла?

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

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

Этот промежуток, интервал, следует выбранной последовательности, такой как оригинальная последовательность Шелла, Кнута, Хиббарда или Седжвика. Оригинальная последовательность Шелла — это n/2, n/4, ..., 1.

Алгоритм сортировки Шелла

Шаг 1) Инициализируйте интервальное значение h = n/2, где n — размер массива.

Шаг 2) Поместите все элементы, находящиеся на расстоянии, равном интервалу h, в подсписок.

Шаг 3) Отсортируйте каждый подсписок с помощью сортировки вставками.

Шаг 4) Установите новый интервал h = h/2.

Шаг 5) Если h > 0, вернитесь к шагу 2. В противном случае перейдите к шагу 6.

Шаг 6) Полученный массив теперь полностью отсортирован.

Как работает сортировка Шелла

При сортировке вставками элементы перемещаются только на одну позицию за раз. Сортировка Шелла, напротив, делит массив на подсписки с большим интервалом и применяет сортировку вставками к каждому подсписку.

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

Принцип работы алгоритма сортировки Шелла на примере.

Давайте отсортируем массив ниже, используя сортировку Шелла.

Шаг 1) Размер массива равен 8, поэтому начальное значение интервала равно h = 8/2 = 4.

Шаг 2) Группируйте элементы на расстоянии че��ырех позиций друг от друга. Подсписки: {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Шаг 3) Отсортируйте каждый подсписок с помощью сортировки вставками. Временная переменная хранит значение, которое помещается в список, пока элементы перемещаются. После перестановок массив будет выглядеть следующим образом.

Шаг 4) Уменьшите интервал. Новый интервал равен h = 4/2 = 2.

Шаг 5) Поскольку 2 > 0, вернитесь к шагу 2 и сгруппируйте элементы на расстоянии двух позиций друг от друга: {1, 5, 8, 7} и {4, 2, 6, 3}.

Отсортируйте первый подсписок. Массив примет следующий вид:

После сортировки второго подсписка:

Уменьшите интервал еще раз до h = 2/2 = 1. С интервалом в один символ сортировка Шелла выполняет заключительный проход сортировки вставками по всему массиву, как показано ниже.

Шаг 6) Повторное деление интервала дает 0. Теперь массив полностью отсортирован:

псевдо-Code для сортировки Shell

Start
Input array a of size n
for (interval = n / 2; interval > 0; interval /= 2)
    for (i = interval; i < n; i += 1)
        temp = a[i];
        for (j = i; j >= interval && a[j - interval] > temp; j -= interval)
            a[j] = a[j - interval];
        a[j] = temp;
End

Программа сортировки Шелла на C/C++

Входной сигнал:

//Shell Sort Program in C/C++
#include <bits/stdc++.h>
using namespace std;
void ShellSort(int data[], int size) {
    for (int interval = size / 2; interval > 0; interval /= 2) {
        for (int i = interval; i < size; i += 1) {
            int temp = data[i];
            int j;
            for (j = i; j >= interval && data[j - interval] > temp; j -= interval) {
                data[j] = data[j - interval];
            }
            data[j] = temp;
        }
    }
}
int main() {
    int data[] = {8, 6, 7, 2, 1, 4, 5, 3};
    int size = sizeof(data) / sizeof(data[0]);
    ShellSort(data, size);
    cout << "Sorted Output: \n";
    for (int i = 0; i < size; i++)
        cout << data[i] << " ";
    cout << "\n";
}

Выход:

Sorted Output:

1 2 3 4 5 6 7 8

Пример сортировки Шелла в Python

Входной сигнал:

#Shell Sort Example in Python
def ShellSort(data, size):
    interval = size // 2
    while interval > 0:
        for i in range(interval, size):
            temp = data[i]
            j = i
            while j >= interval and data[j - interval] > temp:
                data[j] = data[j - interval]
                j -= interval
            data[j] = temp
        interval //= 2
data = [8, 6, 7, 2, 1, 4, 5, 3]
ShellSort(data, len(data))
print('Sorted Output:')
print(data)

Выход:

Sorted Output:
[1, 2, 3, 4, 5, 6, 7, 8]

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

Сортировка Шелла по-прежнему используется в современных системах, где важны объем стека или простота.

• ядро Linux Используется алгоритм сортировки Шелла в тех случаях, когда важно избежать стека вызовов.
• Встроенная библиотека C uClibc использует алгоритм сортировки Shell для снижения потребления памяти.
• В bzip2 используется сортировка Шелла, чтобы избежать глубокой рекурсии во время блочной сортировки.
• Встроенное программное обеспечение отдает предпочтение сортировке Шелла для небольших наборов данных, где рекурсия ограничена.

Преимущества и недостатки сортировки Shell

Анализ сложности сортировки Шелла

Временная сложность сортировки Шелла

Временная сложность алгоритма сортировки Шелла зависит от используемой последовательности пропусков.

В лучшем случае, когда массив уже почти упорядочен, каждый проход требует лишь логарифмического числа проверок, что дает O(n log n).

В худшем случае массив устроен таким образом, что элементам требуется максимальное количество сравнений, и в итоге приращение становится более сложным (O(n^2)) при использовании исходной последовательности Шелла.

1. сложность в лучшем случае: O(n log n)
2. Средняя сложность: от O(n log n) до O(n^(4/3)) в зависимости от последовательности пропусков.
3. Наихудшая сложность: O(n^2) с исходной последовательностью Шелла.

Вопрос о том, какая последовательность пропусков является оптимальной для общего использования, остается открытым, хотя последовательности Седжвика и Чиуры хорошо зарекомендовали себя на практике.

Пространственная сложность сортировки Шелла

Сортировка Шелла не требует вспомогательных массивов, поэтому пространственная сложность составляет O(1) независимо от размера входных данных, что является одним из ее наиболее сильных практических преимуществ.

Часто задаваемые вопросы (FAQ)