Алгоритм сортировки Шелла с ПРИМЕРОМ
Сара Чен
Что такое сортировка Шелла
Метод Шелла, или сортировка Шелла в структуре данных, представляет собой эффективный алгоритм сортировки сравнением на месте. Он назван в честь Дональда Шелла, когда он предложил первоначальную идею еще в 1959 году. Сортировка Шелла — это обобщенное расширение алгоритма сортировки вставками.
Фундаментальная идея этого алгоритма сортировки состоит в том, чтобы сгруппировать элементы, находящиеся далеко друг от друга, и соответствующим образом отсортировать их. Затем постепенно уменьшайте промежуток между ними. Сортировка Шелла преодолевает среднюю сложность сортировки вставками по времени за счет сравнения и обмена элементами, которые находятся далеко.
Этот разрыв, известный как интервал, сокращается в соответствии с некоторыми оптимальными последовательностями разрывов. Время выполнения сортировки оболочки также зависит от этих последовательностей. Существует несколько последовательностей пробелов, таких как исходная последовательность Шелла, формула Кнута, приращения Хиббарда и т. Д. Исходная последовательность пробелов Шелла: n/2, n/4, n/8, ……….1
Алгоритм сортировки Шелла
Шаги или процедура алгоритма сортировки оболочки следующие:
Шаг 1) Инициализируйте значение интервала, h = n/2. (В этом примере n — размер массива)
Шаг 2) Поместите все элементы в пределах интервала h в подсписок.
Шаг 3) Отсортируйте эти подсписки, используя сортировку вставкой.
Шаг 4) Установите новый интервал, h=h/2.
Шаг 5) Если h>0, переходим к шагу 2. В противном случае переходим к шагу 6.
Шаг 6) Результатом будет отсортированный массив.
Как работает сортировка Шелла
При сортировке вставкой элементы перемещаются только на одну позицию за раз. Напротив, сортировка оболочки делит массив на более мелкие части на основе значения интервала и выполняет сортировку вставкой для этих частей.
Постепенно значение интервала уменьшается, а размер разделяемых частей увеличивается. Поскольку части заранее сортируются по отдельности, объединение этих частей требует меньше шагов, чем сортировка вставок.
Следующий GIF-изображение демонстрирует демонстрацию сортировки оболочки. В этой демонстрации красный и синий значения сравниваются и меняются местами на основе сортировки вставкой. Затем интервал уменьшается, и сортировка оболочки инициирует сортировку вставкой в почти отсортированные данные.
Работа алгоритма сортировки Шелла
Давайте рассмотрим следующий пример алгоритма сортировки Шелла. В этом примере мы отсортируем следующий массив с помощью сортировки Шелла:
Шаг 1) Здесь размер массива равен 8. Таким образом, значение интервала будет h = 8/2 или 4.
Шаг 2) Теперь мы будем хранить все элементы на расстоянии 4. В нашем случае это подсписки: {8, 1}, {6, 4}, {7, 5}, {2, 3}.
Шаг 3) Теперь эти подсписки будут отсортированы с использованием сортировки вставкой, где временная переменная используется для сравнения обоих чисел и соответствующей сортировки.
После перестановки операций массив будет выглядеть следующим образом:
Шаг 4) Теперь уменьшим начальное значение интервала. Новый интервал будет h=h/2 или 4/2 или 2.
Шаг 5) Поскольку 2>0, мы перейдем к шагу 2, чтобы сохранить все элементы на расстоянии 2. На этот раз подсписки:
{1, 5, 8, 7}, {4, 2, 6, 3}
Затем эти подсписки будут отсортированы с помощью сортировки вставкой. После сравнения и замены первого подсписка массив будет выглядеть следующим образом.
После сортировки второго подсписка исходный массив будет иметь вид:
Затем интервал снова будет уменьшен. Теперь интервал будет h=h/2, 2/1 или 1. Следовательно, мы будем использовать алгоритм сортировки вставками для сортировки измененного массива.
Ниже приведено пошаговое описание процедуры сортировки вставкой.
Интервал снова делится на 2. К этому моменту интервал становится равным 0. Итак, переходим к шагу 6.
Шаг 6) Поскольку интервал равен 0, к этому времени массив уже отсортирован. Сортированный массив —
Псевдокод
Start
Input array an of size n
for (interval = n / 2; interval & gt; 0; interval /= 2)
for (i = interval; i & lt; n; i += 1)
temp = a[i];
for (j = i; j & gt; = interval & amp; & amp; a[j - interval] & gt; 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 потому что он не использует стек вызовов.
- Библиотека uClibc использует сортировку Шелла.
- Компрессор bzip2 использует сортировку Шелла, чтобы избежать превышения рекурсии.
Преимущества и недостатки сортировки Шелла
| Наши преимущества | Недостатки бонуса без депозита |
|---|---|
| Никакого вызова стека не требуется. | Неэффективно для массивов огромных размеров. |
| Легкая реализация. | Неэффективно для широко распространенных элементов. |
| Эффективен для менее широко расположенных элементов. |
Анализ сложности сортировки Шелла
Временная сложность сортировки Шелла
Временная сложность алгоритма сортировки Шелла составляет O(n^2). Рассуждения следующие:
В лучшем случае общее количество тестов для всех интервалов, когда массив был предварительно упорядочен, равно log n. Таким образом, сложность будет O(n*log n).
В худшем случае давайте предположим, что массив составлен таким образом, что элементы требуют наибольшего количества сравнений. Тогда все элементы не будут сравниваться и переключаться до последней итерации. Таким образом, общее количество сравнений, необходимых для окончательного приращения, равно O(n^2).
В заключение временные сложности будут
- сложность наибольшего случая: O(n*log n)
- Средняя сложность случая: O(n*log n)
- Сложность в худшем случае: O(n^2)
Сложность выполнения сортировки оболочки во многом зависит от используемых последовательностей приращений промежутков. Однако наилучшая последовательность приращений для сортировки оболочки до сих пор неизвестна.
Пространственная сложность сортировки Шелла
В этой сравнительной сортировке нам не нужно никакого дополнительного вспомогательного пространства. Таким образом, пространственная сложность этого вида алгоритма составляет O(1).
