Algoritmus řazení Shell s PŘÍKLADEM
Sarah Chen
Co je Shell Sort
Shellova metoda neboli Shell sort ve struktuře dat je účinným algoritmem řazení na místě. Je pojmenován po Donaldu Shellovi, když v roce 1959 navrhl původní myšlenku. Shell sort je zobecněné rozšíření algoritmu řazení vkládání.
Základní myšlenkou tohoto třídícího algoritmu je seskupit prvky, které jsou daleko od sebe, a podle toho je seřadit. Poté postupně zmenšujte mezeru mezi nimi. Shell sort překonává průměrnou časovou složitost typu vkládání porovnáváním a výměnou prvků, které jsou daleko.
Tato mezera, známá jako interval, je redukována podle některých optimálních sekvencí mezer. Na těchto sekvencích závisí také doba běhu řazení shellu. Existuje několik mezerových sekvencí, jako je původní sekvence Shell, Knuthův vzorec, Hibbardovy přírůstky atd. Původní sekvence mezer Shell je – n/2, n/4, n/8, ……….1
Algoritmus řazení Shell
Kroky nebo postup pro algoritmus řazení shellu jsou následující-
Krok 1) Inicializujte hodnotu intervalu, h = n/2. (V tomto příkladu je n velikost pole)
Krok 2) Dejte všechny prvky ve vzdálenosti intervalu h do dílčího seznamu.
Krok 3) Seřaďte tyto podseznamy pomocí řazení vložení.
Krok 4) Nastavte nový interval, h=h/2.
Krok 5) Pokud h>0, přejděte ke kroku 2. Jinak přejděte ke kroku 6.
Krok 6) Výsledným výstupem bude setříděné pole.
Jak Shell Sort funguje
Při řazení vložení se prvky posunou vždy pouze o jednu pozici. Naopak, Shell sort rozdělí pole na menší části na základě hodnoty intervalu a na těchto částech provede řazení vložení.
Postupně se hodnota intervalu snižuje a velikost rozdělených kusů se zvětšuje. Vzhledem k tomu, že kusy jsou předem individuálně tříděny, sloučení těchto kusů vyžaduje méně kroků než sloučení řazení řazení.
Následující GIF ukazuje ukázku řazení shellu. V této ukázce se červená a modrá indikovaná hodnota porovná a zamění na základě řazení vložení. Potom se interval zmenší a řazení shellu zahájí řazení vložení do téměř setříděných dat.
Fungování algoritmu řazení Shell
Podívejme se na následující příklad algoritmu řazení shellu. V tomto příkladu seřadíme následující pole pomocí shell sort:
Krok 1) Zde je velikost pole 8. Hodnota intervalu tedy bude h = 8/2 nebo 4.
Krok 2) Nyní uložíme všechny prvky ve vzdálenosti 4. Pro náš případ jsou podseznamy- {8, 1}, {6, 4}, {7, 5}, {2, 3}.
Krok 3) Nyní budou tyto podseznamy řazeny pomocí řazení vložení, kde se k porovnání obou čísel a odpovídajícímu řazení používá dočasná proměnná.
Pole by po výměně operací vypadalo jako následující -
Krok 4) Nyní snížíme počáteční hodnotu intervalu. Nový interval bude h=h/2 nebo 4/2 nebo 2.
Krok 5) Jako 2>0 přejdeme ke kroku 2, abychom uložili všechny prvky ve vzdálenosti 2. Pro tentokrát jsou dílčí seznamy-
{1, 5, 8, 7}, {4, 2, 6, 3}
Poté budou tyto podseznamy seřazeny pomocí řazení vložení. Po porovnání a prohození prvního dílčího seznamu bude pole následující.
Po seřazení druhého podseznamu bude původní pole:
Poté se interval opět sníží. Nyní bude interval h=h/2 nebo 2/1 nebo 1. Pro třídění upraveného pole tedy použijeme algoritmus řazení vložení.
Následuje postupné znázornění řazení vkládání krok za krokem.
Interval je opět dělen 2. Do této doby je interval 0. Takže přejdeme ke kroku 6.
Krok 6) Protože je interval 0, je pole seřazeno podle tohoto času. Seřazené pole je -
Pseudo kód
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 řazení Shell v C/C++
Vstup:
//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";
}
Výstup:
Sorted Output: 1 2 3 4 5 6 7 8
Příklad řazení Shell v Python
Vstup:
#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)
Výstup:
Sorted Output: [1, 2, 3, 4, 5, 6, 7, 8]
Aplikace Shell Sort
Zde jsou důležité aplikace Shell Sort:
- Shell sort se používá v Linux kernel protože nepoužívá zásobník volání.
- Knihovna uClibc používá řazení Shell.
- Kompresor bzip2 používá řazení Shell k zastavení překračování rekurze.
Výhody a nevýhody Shell Sort
| Výhody | Nevýhody |
|---|---|
| Není vyžadováno žádné volání zásobníku. | Neefektivní pro velké velikosti polí. |
| Snadná implementace. | Neefektivní pro široce rozšířené prvky. |
| Efektivní pro méně rozmístěné prvky. |
Analýza složitosti řazení Shell
Časová složitost řazení Shell
Časová složitost algoritmu řazení shellu je O(n^2). Odůvodnění je následující:
V nejlepším případě se celkový počet testů pro všechny intervaly, kdy bylo pole dříve uspořádáno, rovná log n. Složitost by tedy byla O(n*log n).
Pro nejhorší scénář uvažujme, že pole se skládá tak, že prvky vyžadují nejvyšší počet srovnání. Pak nebudou všechny prvky porovnávány a přepínány až do poslední iterace. Celkové porovnání požadované pro konečný přírůstek je tedy O(n^2).
Závěrem, časové složitosti by byly
- Nejlepší případová složitost: O(n*log n)
- Průměrná složitost případu: O(n*log n)
- Složitost nejhoršího případu: O(n^2)
Složitost doby běhu řazení shellu silně závisí na použitých sekvencích přírůstku mezery. Nejlepší sekvence přírůstků pro řazení shellu je však stále neznámá.
Shell Sort Space Složitost
V tomto srovnání nepotřebujeme žádný další pomocný prostor. Prostorová složitost tohoto druhu algoritmu je tedy O(1).
