Skallsorteringsalgoritme med EKSEMPEL
Sarah Chen
Hva er Shell Sort
Shells metode, eller Shell-sortering i datastruktur, er en effektiv sammenligningssorteringsalgoritme på stedet. Den er oppkalt etter Donald Shell da han foreslo den første ideen tilbake i 1959. Shell-sortering er en generalisert utvidelse av innsettingssorteringsalgoritmen.
Den grunnleggende ideen med denne sorteringsalgoritmen er å gruppere elementene som er langt fra hverandre og sortere dem deretter. Reduser deretter gapet mellom dem gradvis. Shell-sortering overvinner den gjennomsnittlige sakstidskompleksiteten til innsettingssortering ved å sammenligne og utveksle elementer som er langt unna.
Dette gapet, kjent som intervallet, reduseres i henhold til noen optimale gapsekvenser. Kjøretiden for skallsortering er også avhengig av disse sekvensene. Det er flere gap-sekvenser, for eksempel Shells opprinnelige sekvens, Knuths formel, Hibbards inkrementer, etc. Shells opprinnelige gap-sekvens er – n/2, n/4, n/8, ……….1
Algoritme for skjellsortering
Trinnene eller prosedyren for skallsorteringsalgoritmen er som følger-
Trinn 1) Initialiser intervallverdien, h = n/2. (I dette eksemplet er n størrelsen på matrisen)
Trinn 2) Sett alle elementene innenfor en avstand fra intervallet h i en underliste.
Trinn 3) Sorter disse underlistene ved å bruke innsettingssortering.
Trinn 4) Sett nytt intervall, h=h/2.
Trinn 5) Hvis h>0, gå til trinn 2. Ellers gå til trinn 6.
Trinn 6) Den resulterende utgangen vil være den sorterte matrisen.
Hvordan Shell Sort fungerer
Ved innsettingssortering flyttes elementer kun med én posisjon om gangen. Tvert imot deler shell-sortering arrayet i mindre biter basert på intervallverdien og utfører innsettingssortering på disse brikkene.
Gradvis synker intervallverdien, og størrelsen på de delte brikkene øker. Siden brikkene er individuelt sortert på forhånd, krever sammenslåing av disse delene færre trinn enn innsettings sortering.
Følgende GIF viser en demonstrasjon av skjellsortering. I denne demoen blir den røde og den blå angitte verdien sammenlignet og byttet basert på innsettingssortering. Deretter reduseres intervallet, og shell-sortering starter innsettingssortering i de nesten sorterte dataene.
Arbeid av Shell Sort Algorithm
La oss se et følgende eksempel på en skjellsorteringsalgoritme. I dette eksemplet vil vi sortere følgende array ved å bruke shell sort:
Trinn 1) Her er matrisestørrelsen 8. Dermed vil intervallverdien være h = 8/2 eller 4.
Trinn 2) Nå vil vi lagre alle elementene i en avstand på 4. For vårt tilfelle er underlistene- {8, 1}, {6, 4}, {7, 5}, {2, 3}.
Trinn 3) Nå vil disse underlistene sorteres ved hjelp av innsettingssortering, der en midlertidig variabel brukes til å sammenligne begge tallene og sortere deretter.
Matrisen vil være som følgende etter bytte av operasjoner-
Trinn 4) Nå vil vi redusere startverdien til intervallet. Det nye intervallet vil være h=h/2 eller 4/2 eller 2.
Trinn 5) Som 2>0 vil vi gå til trinn 2 for å lagre alle elementene i en avstand på 2. For denne gang er underlistene-
{1, 5, 8, 7}, {4, 2, 6, 3}
Deretter vil disse underlistene bli sortert ved hjelp av innsettingssortering. Etter å ha sammenlignet og byttet den første underlisten, vil matrisen være følgende.
Etter sortering av den andre underlisten, vil den opprinnelige matrisen være:
Så igjen vil intervallet reduseres. Nå vil intervallet være h=h/2 eller 2/1 eller 1. Derfor vil vi bruke innsettingssorteringsalgoritmen for å sortere den modifiserte matrisen.
Følgende er den trinnvise prosedyreskildringen av innsettingssortering.
Intervallet blir igjen delt på 2. På dette tidspunktet blir intervallet 0. Så vi går til trinn 6.
Trinn 6) Siden intervallet er 0, sorteres matrisen etter denne tiden. Den sorterte matrisen er-
Pseudo-kode
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 Sorteringsprogram i C/C++
Inngang:
//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";
}
Utgang:
Sorted Output: 1 2 3 4 5 6 7 8
Shell Sorter eksempel i Python
Inngang:
#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)
Utgang:
Sorted Output: [1, 2, 3, 4, 5, 6, 7, 8]
Applikasjoner av Shell Sort
Her er viktige bruksområder for Shell Sort:
- Skallsortering brukes i Linux-kjernen fordi den ikke bruker en anropsstabel.
- uClibc-biblioteket bruker Shell-sortering.
- bzip2-kompressor bruker Shell-sortering for å slutte å overskride rekursjon.
Fordeler og ulemper med Shell Sort
| Fordeler | Ulemper |
|---|---|
| Ingen stabelkall er nødvendig. | Ikke effektiv for store matrisestørrelser. |
| Enkel implementering. | Ineffektiv for vidt spredte elementer. |
| Effektiv for elementer med mindre avstand. |
Shell Sort kompleksitetsanalyse
Tidskompleksiteten til Shell Sort
Tidskompleksiteten til skallsorteringsalgoritmen er O(n^2). Begrunnelsen er som følger:
For det beste scenarioet, den totale mengden tester for alle intervaller når matrisen tidligere ble arrangert lik log n. Dermed vil kompleksiteten være O(n*log n).
For det verste scenariet, la oss vurdere at matrisen består på en slik måte at elementene krever det høyeste antallet sammenligninger. Da vil ikke alle elementene sammenlignes og byttes før siste iterasjon. Derfor er den totale sammenligningen som kreves for den endelige økningen O(n^2).
Avslutningsvis vil tidskompleksiteten være
- Beste sakskompleksitet: O(n*log n)
- Gjennomsnittlig sakskompleksitet: O(n*log n)
- Verste tilfelle kompleksitet: O(n^2)
Kjøretidskompleksiteten til shell-sortering avhenger sterkt av gap-inkrementsekvensene som brukes. Imidlertid er den beste økningssekvensen for skjellsortering fortsatt ukjent.
Shell Sort Space kompleksitet
I denne sammenligningstypen trenger vi ikke noe ekstra plass. Dermed er romkompleksiteten til denne typen algoritme O(1).
