Algoritam za sortiranje ljuske s PRIMJEROM
Sarah Chen
Što je Shell Sort
Shellova metoda, ili Shell sortiranje u strukturi podataka, učinkovit je algoritam sortiranja za usporedbu na mjestu. Nazvan je po Donaldu Shellu kada je 1959. predložio početnu ideju. Shell sort je generalizirano proširenje algoritma sortiranja umetanjem.
Temeljna ideja ovog algoritma sortiranja je grupirati elemente koji su međusobno udaljeni i sortirati ih u skladu s tim. Zatim postupno smanjite razmak između njih. Shell sortiranje nadilazi prosječnu složenost slučaja i vremena sortiranja umetanjem usporedbom i razmjenom elemenata koji su udaljeni.
Ovaj razmak, poznat kao interval, smanjuje se prema nekim optimalnim sekvencama razmaka. Vrijeme rada shell sortiranja također ovisi o tim sekvencama. Postoji nekoliko nizova praznina, kao što je Shellov izvorni niz, Knuthova formula, Hibbardovi prirasta, itd. Shellov izvorni niz praznina je – n/2, n/4, n/8, ……….1
Algoritam sortiranja ljuske
Koraci ili postupak za algoritam sortiranja ljuske su sljedeći:
Korak 1) Inicijalizirajte vrijednost intervala, h = n/2. (U ovom primjeru, n je veličina niza)
Korak 2) Stavite sve elemente unutar udaljenosti od intervala h u podlistu.
Korak 3) Razvrstajte te podpopise pomoću sortiranja umetanjem.
Korak 4) Postavite novi interval, h=h/2.
Korak 5) Ako je h>0, idite na korak 2. Inače idite na korak 6.
Korak 6) Rezultirajući izlaz bit će sortirani niz.
Kako Shell Sort radi
Kod sortiranja umetanjem, elementi se pomiču samo za jednu poziciju u isto vrijeme. Naprotiv, shell sortiranje dijeli niz na manje dijelove na temelju vrijednosti intervala i izvršava sortiranje umetanjem na tim dijelovima.
Postupno se vrijednost intervala smanjuje, a veličina podijeljenih dijelova povećava. Budući da se dijelovi prethodno pojedinačno razvrstavaju, spajanje tih dijelova zahtijeva manje koraka od spajanja umetanje sortirati.
Sljedeći GIF prikazuje demonstraciju sortiranja ljuske. U ovoj demonstraciji crveno i plavo naznačene vrijednosti uspoređuju se i mijenjaju na temelju sortiranja umetanjem. Tada se interval smanjuje, a sortiranje ljuske pokreće sortiranje umetanjem u te gotovo sortirane podatke.
Rad algoritma sortiranja ljuske
Pogledajmo sljedeći primjer algoritma sortiranja ljuske. U ovom primjeru sortirat ćemo sljedeći niz pomoću shell sortiranja:
Korak 1) Ovdje je veličina niza 8. Stoga će vrijednost intervala biti h = 8/2 ili 4.
Korak 2) Sada ćemo sve elemente pohraniti na udaljenosti od 4. Za naš slučaj, podliste su- {8, 1}, {6, 4}, {7, 5}, {2, 3}.
Korak 3) Sada će ti podpopisi biti sortirani pomoću sortiranja umetanjem, gdje se privremena varijabla koristi za usporedbu oba broja i sortiranje u skladu s tim.
Niz bi bio sljedeći nakon operacija zamjene-
Korak 4) Sada ćemo smanjiti početnu vrijednost intervala. Novi interval će biti h=h/2 ili 4/2 ili 2.
Korak 5) Kako je 2>0, ići ćemo na korak 2 da pohranimo sve elemente na udaljenosti od 2. Za ovo vrijeme, podliste su-
{1, 5, 8, 7}, {4, 2, 6, 3}
Zatim će ti podlisti biti sortirani pomoću sortiranja umetanjem. Nakon usporedbe i zamjene prve podliste, niz bi bio sljedeći.
Nakon sortiranja druge podliste, originalni niz će biti:
Tada će se opet interval smanjiti. Sada će interval biti h=h/2 ili 2/1 ili 1. Stoga ćemo koristiti algoritam sortiranja umetanjem za sortiranje modificiranog niza.
Slijedi detaljan opis postupka sortiranja umetanjem.
Interval se ponovno dijeli s 2. Do tog vremena interval postaje 0. Dakle, idemo na korak 6.
Korak 6) Kako je interval 0, niz je sortiran prema ovom vremenu. Sortirani niz je-
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
Shell Sort Program u C/C++
Ulazni:
//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";
}
Izlaz:
Sorted Output: 1 2 3 4 5 6 7 8
Shell Sort Primjer u Python
Ulazni:
#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)
Izlaz:
Sorted Output: [1, 2, 3, 4, 5, 6, 7, 8]
Primjene Shell Sort
Evo važnih primjena Shell Sort-a:
- Shell sort se koristi u Linux kernel jer ne koristi pozivni stog.
- uClibc biblioteka koristi Shell sortiranje.
- bzip2 kompresor koristi Shell sortiranje da zaustavi prekoračenje rekurzije.
Prednosti i nedostaci Shell sortiranja
| Prednosti | Nedostaci |
|---|---|
| Nije potreban poziv snopa. | Nije učinkovito za velike veličine nizova. |
| Jednostavna implementacija. | Neučinkovit za široko rasprostranjene elemente. |
| Učinkovito za manje razmaknute elemente. |
Shell Sort Complexity Analiza
Vremenska složenost shell sortiranja
Vremenska složenost algoritma sortiranja ljuske je O(n^2). Obrazloženje je sljedeće:
U najboljem slučaju, ukupna količina testova za sve intervale kada je niz prethodno raspoređen jednak je log n. Stoga bi složenost bila O(n*log n).
Za najgori mogući scenarij, uzmimo u obzir da se niz sastoji na takav način da elementi zahtijevaju najveći broj usporedbi. Tada se svi elementi neće uspoređivati i mijenjati do zadnje iteracije. Stoga je ukupna usporedba potrebna za konačno povećanje O(n^2).
Zaključno, vremenska složenost bila bi
- Složenost u najboljem slučaju: O(n*log n)
- Prosječna složenost slučaja: O(n*log n)
- Složenost u najgorem slučaju: O(n^2)
Složenost vremena izvođenja shell sortiranja uvelike ovisi o korištenim sekvencama povećanja praznina. Međutim, još uvijek nije poznat najbolji redoslijed povećanja za shell sort.
Shell Sort Space Complexity
U ovoj usporednoj vrsti ne trebamo nikakav dodatni pomoćni prostor. Stoga je prostorna složenost ove vrste algoritma O(1).
