Алгоритъм за сортиране по Shell с пример

Какво е сортиране по Shell?

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

Основната идея е да се групират елементи, които са отдалечени един от друг, да се сортира всяка група чрез сортиране с вмъкване и да се свива разстоянието стъпка по стъпка, докато достигне единица. До този момент масивът е почти сортиран.

Тази празнина, интервалът, следва избрана последователност, като например оригиналната на Шел, на Кнут, на Хибард или на Седжуик. Оригиналът на Шел е n/2, n/4, ..., 1.

Алгоритъм за сортиране на Shell

Стъпка 1) Инициализирайте интервалната стойност h = n/2, където n е размерът на масива.

Стъпка 2) Поставете всички елементи в рамките на разстояние от интервала h в подсписък.

Стъпка 3) Сортирайте всеки подсписък, използвайки сортиране с вмъкване.

Стъпка 4) Задайте нов интервал h = h/2.

Стъпка 5) Ако h > 0, върнете се към стъпка 2. В противен случай преминете към стъпка 6.

Стъпка 6) Полученият масив вече е напълно сортиран.

Как работи Shell Sort

При сортирането с вмъкване, елементите се местят само с една позиция наведнъж. Shell Sort вместо това разделя масива на широко разположени подсписъци въз основа на интервала и изпълнява сортиране с вмъкване за всеки подсписък.

С намаляването на интервала, размерът на подсписъка нараства. Тъй като по-ранните преминавания оставят данните частично сортирани, по-малките интервали изискват много по-малко размени, отколкото изпълнението вмъкване сортиране от нулата. Фигурата по-долу илюстрира един проход на сортиране по Shell.

Работа на алгоритъма за сортиране по Shell с пример

Нека сортираме масива по-долу, използвайки Shell Sort.

Стъпка 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. С интервал от едно, Shell Sort изпълнява последен цикъл на сортиране с вмъкване върху целия масив, както е показано по-долу.

Стъпка 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

Програма за сортиране на Shell в 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

Shell Пример за сортиране в 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]

Приложения на Shell Sort

Shell сортирането все още се среща в съвременните системи, където пространството на стека или простотата имат значение.

• - Linux ядрото използва Shell Sort на места, където избягването на стек от повиквания е от значение.
• Вградената C библиотека uClibc използва Shell Sort, за да поддържа ниско потребление на памет.
• bzip2 използва Shell Sort, за да избегне дълбока рекурсия по време на блоково сортиране.
• Вграденият фърмуер предпочита Shell Sort за малки набори от данни, където рекурсията е ограничена.

Предимства и недостатъци на сортирането по Shell

Анализ на сложността на сортирането на Shell

Времева сложност на Shell Sort

Времевата сложност на Shell Sort зависи от използваната последователност от празнини.

В най-добрия случай, когато масивът е почти подреден, всеки проход изисква само логаритмичен брой тестове, което дава O(n log n).

В най-лошия случай масивът е подреден така, че елементите се нуждаят от максимален брой сравнения, а крайното нарастване доминира при O(n^2) с оригиналната последователност на Shell.

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

Най-добрата последователност от празнини с общо предназначение все още е отворен изследователски въпрос, въпреки че последователностите на Седжвик и Чиура се представят добре на практика.

Shell Sort Space Complexity

Shell Sort не изисква спомагателни масиви, така че пространствената сложност е O(1), независимо от размера на входните данни, което е едно от най-силните му практически предимства.

Въпроси и Отговори