Algorytm sortowania powłoki z przykładem

Czym jest sortowanie muszlowe?

Sortowanie Shella, zwane również metodą Shella, to wydajny algorytm sortowania oparty na porównaniach w miejscu. Nazwany na cześć Donalda Shella, który wprowadził tę ideę w 1959 roku, jest uogólnionym rozszerzeniem sortowania przez wstawianie, które eliminuje jego kwadratowe zachowanie w przypadku danych rozproszonych.

Podstawową ideą jest grupowanie elementów oddalonych od siebie, sortowanie każdej grupy metodą sortowania przez wstawianie i stopniowe zmniejszanie odstępu, aż do osiągnięcia jednego elementu. Wtedy tablica jest prawie posortowana.

Ta przerwa, interwał, podąża za wybraną sekwencją, taką jak oryginał Shella, Knutha, Hibbarda czy Sedgewicka. Oryginał Shella to n/2, n/4, ..., 1.

Algorytm sortowania powłoki

Krok 1) Zainicjuj wartość interwału h = n/2, gdzie n jest rozmiarem tablicy.

Krok 2) Umieść wszystkie elementy w odległości od przedziału h na podliście.

Krok 3) Posortuj każdą podlistę, używając sortowania przez wstawianie.

Krok 4) Ustaw nowy przedział h = h/2.

Krok 5) Jeżeli h > 0, wróć do kroku 2. W przeciwnym razie przejdź do kroku 6.

Krok 6) Powstała tablica jest teraz całkowicie posortowana.

Jak działa sortowanie powłoki

W sortowaniu przez wstawianie elementy przesuwają się tylko o jedną pozycję na raz. Sortowanie przez powłokę dzieli tablicę na szeroko rozstawione podlisty w oparciu o interwał i przeprowadza sortowanie przez wstawianie dla każdej podlisty.

Wraz ze zmniejszaniem się interwału, rozmiar podlisty rośnie. Ponieważ wcześniejsze przebiegi pozostawiają dane częściowo posortowane, mniejsze interwały wymagają znacznie mniej zamian niż w przypadku sortowanie przez wstawianie od podstaw. Poniższy rysunek ilustruje jedno przejście sortowania Shell.

Działanie algorytmu sortowania powłoki z przykładem

Posortujmy poniższą tablicę, korzystając z sortowania powłoki.

Krok 1) Rozmiar tablicy wynosi 8, więc początkowa wartość przedziału wynosi h = 8/2 = 4.

Krok 2) Elementy grupy oddalone od siebie o cztery pozycje. Podlisty: {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Krok 3) Posortuj każdą podlistę, używając sortowania przez wstawianie. Zmienna tymczasowa przechowuje wartość umieszczaną podczas przesuwania elementów. Po zamianie elementów tablica wygląda tak.

Krok 4) Zmniejsz przedział. Nowy przedział to h = 4/2 = 2.

Krok 5) Ponieważ 2 > 0, wróć do kroku 2 i zgrupuj elementy oddalone od siebie o dwie pozycje: {1, 5, 8, 7} i {4, 2, 6, 3}.

Posortuj pierwszą podlistę. Tablica będzie wyglądać następująco:

Po posortowaniu drugiej podlisty:

Ponownie zmniejsz interwał do h = 2/2 = 1. Przy odstępie równym jeden sortowanie powłoki uruchamia ostatni cykl sortowania przez wstawianie w całej tablicy, jak pokazano poniżej.

Krok 6) Ponowne podzielenie przedziału daje 0. Tablica jest teraz w pełni posortowana:

Rzekomy-Code do sortowania muszli

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

Program sortowania powłoki w C/C++

Wejście:

//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";
}

Wyjście:

Sorted Output:

1 2 3 4 5 6 7 8

Przykład sortowania powłoki w Python

Wejście:

#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)

Wyjście:

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

Zastosowania sortowania skorupowego

Sortowanie Shella nadal jest stosowane w nowoczesnych systemach, w których liczy się przestrzeń stosu lub prostota.

• jądro Linux używa Shell Sort w miejscach, w których unikanie stosu wywołań ma znaczenie.
• Wbudowana biblioteka języka C uClibc wykorzystuje sortowanie powłoki w celu utrzymania niskiego zużycia pamięci.
• bzip2 używa Shell Sort, aby uniknąć głębokiej rekurencji podczas sortowania bloków.
• Oprogramowanie sprzętowe preferuje sortowanie powłoki w przypadku małych zestawów danych, w których rekursja jest ograniczona.

Zalety i wady sortowania muszlowego

Analiza złożoności sortowania muszli

Złożoność czasowa sortowania powłoki

Złożoność czasowa sortowania Shella zależy od użytej sekwencji przerw.

W najlepszym przypadku, gdy tablica jest już prawie uporządkowana, każde przejście wymaga jedynie logarytmicznej liczby testów, co daje O(n log n).

W najgorszym przypadku tablica jest ułożona tak, aby elementy wymagały maksymalnej liczby porównań, a końcowy przyrost dominuje przy O(n^2) zgodnie z oryginalną sekwencją Shella.

1. Złożoność w najlepszym przypadku: O(n log n)
2. Złożoność przypadku średniego: od O(n log n) do O(n^(4/3)) w zależności od sekwencji przerw
3. Najgorszy przypadek złożoności: O(n^2) z oryginalną sekwencją Shella

Najlepsza uniwersalna sekwencja luk wciąż pozostaje otwartym pytaniem badawczym, chociaż sekwencje Sedgewicka i Ciury dobrze sprawdzają się w praktyce.

Złożoność przestrzenna sortowania muszli

Sortowanie Shell nie wymaga tablic pomocniczych, więc złożoność pamięciowa wynosi O(1) niezależnie od rozmiaru danych wejściowych, co jest jedną z jego największych praktycznych zalet.

FAQ