Algorytm sortowania powłoki z PRZYKŁADEM
Sara Chen
Co to jest sortowanie powłoki
Metoda powłoki lub sortowanie powłoki w strukturze danych to wydajny algorytm sortowania porównawczego w miejscu. Został nazwany na cześć Donalda Shella, który zaproponował swój pierwotny pomysł w 1959 roku. Sortowanie powłokowe jest uogólnionym rozszerzeniem algorytmu sortowania przez wstawianie.
Podstawowym założeniem tego algorytmu sortowania jest grupowanie elementów, które są daleko od siebie i sortowanie ich odpowiednio. Następnie stopniowo zmniejszaj odstęp między nimi. Sortowanie powłoki pokonuje średnią złożoność czasową sortowania przez wstawianie, porównując i wymieniając elementy, które są daleko od siebie.
Ta przerwa, zwana interwałem, jest zmniejszana zgodnie z pewnymi optymalnymi sekwencjami przerw. Czas trwania sortowania powłoki jest również zależny od tych sekwencji. Istnieje kilka sekwencji przerw, takich jak pierwotna sekwencja Shella, wzór Knutha, przyrosty Hibbarda itp. Oryginalna sekwencja przerw Shella to – n/2, n/4, n/8, ……….1
Algorytm sortowania powłoki
Kroki lub procedura algorytmu sortowania powłoki jest następująca:
Krok 1) Zainicjuj wartość interwału, h = n/2. (W tym przykładzie n jest rozmiarem tablicy)
Krok 2) Umieść wszystkie elementy w odległości od przedziału h na podliście.
Krok 3) Posortuj te podlisty, korzystając z sortowania przez wstawianie.
Krok 4) Ustaw nowy interwał, h=h/2.
Krok 5) Jeśli h>0, przejdź do kroku 2. W przeciwnym razie przejdź do kroku 6.
Krok 6) Wynikowy wynik będzie posortowaną tablicą.
Jak działa sortowanie powłoki
Podczas sortowania przez wstawianie elementy są przesuwane tylko o jedną pozycję na raz. Wręcz przeciwnie, sortowanie powłokowe dzieli tablicę na mniejsze części w oparciu o wartość interwału i wykonuje sortowanie przez wstawianie tych fragmentów.
Stopniowo wartość interwału maleje, a rozmiar podzielonych elementów wzrasta. Ponieważ elementy są wcześniej indywidualnie sortowane, łączenie ich wymaga mniej kroków niż w przypadku sortowanie przez wstawianie.
Poniższy GIF pokazuje demonstrację sortowania przez powłokę. W tej demonstracji czerwona i niebieska wskazana wartość są porównywane i zamieniane na podstawie sortowania przez wstawianie. Następnie przedział maleje, a sortowanie przez powłokę inicjuje sortowanie przez wstawianie w tych prawie posortowanych danych.
Działanie algorytmu sortowania powłokowego
Zobaczmy następujący przykład algorytmu sortowania powłoki. W tym przykładzie posortujemy następującą tablicę za pomocą sortowania powłoki:
Krok 1) Tutaj rozmiar tablicy wynosi 8. Zatem wartość interwału będzie wynosić h = 8/2 lub 4.
Krok 2) Teraz będziemy przechowywać wszystkie elementy w odległości 4. W naszym przypadku podlistami są: {8, 1}, {6, 4}, {7, 5}, {2, 3}.
Krok 3) Teraz te podlisty zostaną posortowane za pomocą sortowania przez wstawianie, w którym tymczasowa zmienna zostanie użyta do porównania obu liczb i odpowiedniego posortowania.
Tablica po operacjach zamiany będzie wyglądać następująco:
Krok 4) Teraz zmniejszymy początkową wartość przedziału. Nowy odstęp będzie wynosił h=h/2, 4/2 lub 2.
Krok 5) Ponieważ 2>0, przejdziemy do kroku 2, aby zapisać wszystkie elementy w odległości 2. W tym przypadku podlisty to:
{1, 5, 8, 7}, {4, 2, 6, 3}
Następnie te podlisty zostaną posortowane za pomocą sortowania przez wstawianie. Po porównaniu i zamianie pierwszej podlisty, tablica będzie następująca.
Po posortowaniu drugiej podlisty oryginalna tablica będzie wyglądać następująco:
Następnie ponownie odstęp zostanie zmniejszony. Teraz przedział będzie wynosił h=h/2, 2/1 lub 1. Dlatego użyjemy algorytmu sortowania przez wstawianie, aby posortować zmodyfikowaną tablicę.
Poniżej przedstawiono krok po kroku procedurę sortowania przez wstawianie.
Przedział jest ponownie dzielony przez 2. W tym czasie odstęp wynosi 0. Przechodzimy więc do kroku 6.
Krok 6) Ponieważ interwał wynosi 0, tablica jest sortowana według tego czasu. Posortowana tablica to-
Pseudo kod
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
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
Oto ważne zastosowania sortowania skorupowego:
- Sortowanie powłokowe jest używane w jądro Linux ponieważ nie używa stosu wywołań.
- Biblioteka uClibc używa sortowania powłoki.
- Kompresor bzip2 używa sortowania powłoki, aby zatrzymać przekroczenie rekurencji.
Zalety i wady sortowania skorupowego
| Zalety | Niedogodności |
|---|---|
| Nie jest wymagane żadne wywołanie stosu. | Nieefektywne w przypadku dużych rozmiarów tablic. |
| Łatwa implementacja. | Nieefektywne w przypadku szeroko rozpowszechnionych elementów. |
| Skuteczne w przypadku mniej oddalonych od siebie elementów. |
Analiza złożoności sortowania muszli
Złożoność czasowa sortowania powłoki
Złożoność czasowa algorytmu sortowania powłoki wynosi O(n^2). Rozumowanie jest następujące:
W najlepszym przypadku całkowita liczba testów dla wszystkich przedziałów, gdy tablica była wcześniej ułożona, wynosiłaby log n. Zatem złożoność wynosiłaby O(n*log n).
W najgorszym przypadku rozważmy, że tablica składa się w taki sposób, że elementy wymagają największej liczby porównań. Wtedy wszystkie elementy nie będą porównywane i przełączane aż do ostatniej iteracji. Dlatego też całkowite porównania wymagane dla końcowego przyrostu wynoszą O(n^2).
Podsumowując, złożoność czasowa byłaby następująca:
- Najlepsza złożoność przypadku: O(n*log n)
- Średnia złożoność przypadku: O(n*log n)
- Najgorszy przypadek złożoności: O(n^2)
Złożoność czasowa sortowania powłoki w dużym stopniu zależy od użytych sekwencji inkrementacji gap. Jednak najlepsza sekwencja inkrementacji dla sortowania powłoki jest nadal nieznana.
Złożoność przestrzenna sortowania muszli
W tym sortowaniu porównawczym nie potrzebujemy żadnej dodatkowej przestrzeni pomocniczej. Zatem złożoność przestrzenna tego rodzaju algorytmu wynosi O(1).
