Skalsorteringsalgoritme med EKSEMPEL

Hvad er Shell Sort

Shells metode, eller Shell-sortering i datastruktur, er en effektiv in-place-sammenligningssorteringsalgoritme. Den er opkaldt efter Donald Shell, da han foreslog den oprindelige idé tilbage i 1959. Shell-sortering er en generaliseret udvidelse af indsættelsessorteringsalgoritmen.

Den grundlæggende idé med denne sorteringsalgoritme er at gruppere de elementer, der er langt fra hinanden, og sortere dem i overensstemmelse hermed. Formindsk derefter gradvist afstanden mellem dem. Shell-sortering overvinder den gennemsnitlige sagstidskompleksitet af indsættelsessortering ved at sammenligne og udveksle elementer, der er langt væk.

Dette mellemrum, kendt som intervallet, reduceres i henhold til nogle optimale mellemrumssekvenser. Køretiden for skalsortering er også afhængig af disse sekvenser. Der er flere mellemrumssekvenser, såsom Shells oprindelige sekvens, Knuths formel, Hibbards intervaller osv. Shells oprindelige mellemrumssekvens er – n/2, n/4, n/8, ……….1

Skalsorteringsalgoritme

Trinene eller proceduren for shellsorteringsalgoritmen er som følger-

Trin 1) Initialiser intervalværdien, h = n/2. (I dette eksempel er n størrelsen af ​​arrayet)

Trin 2) Sæt alle elementer inden for en afstand af intervallet h i en underliste.

Trin 3) Sorter disse underlister ved hjælp af indsættelsessortering.

Trin 4) Indstil nyt interval, h=h/2.

Trin 5) Hvis h>0, gå til trin 2. Ellers gå til trin 6.

Trin 6) Det resulterende output vil være det sorterede array.

Sådan fungerer Shell-sortering

Ved indsættelsessortering flyttes elementer kun med én position ad gangen. Tværtimod opdeler shell-sortering arrayet i mindre stykker baseret på intervalværdien og udfører indsættelsessortering på disse stykker.

Gradvist falder intervalværdien, og de opdelte stykkers størrelse øges. Da stykkerne er sorteret individuelt på forhånd, kræver det færre trin at fusionere disse stykker end indsætnings sortering.

Følgende GIF viser en demonstration af skalsortering. I denne demo sammenlignes og byttes den røde og den blå angivne værdi baseret på indsættelsessortering. Så falder intervallet, og shell-sortering starter indsættelsessortering i de næsten sorterede data.

Arbejde med Shell Sort Algorithm

Lad os se et følgende eksempel på en shell-sorteringsalgoritme. I dette eksempel vil vi sortere følgende array ved hjælp af shell sort:

Trin 1) Her er matrixstørrelsen 8. Intervalværdien vil således være h = 8/2 eller 4.

Trin 2) Nu vil vi gemme alle elementer i en afstand på 4. For vores tilfælde er underlisterne- {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Trin 3) Nu vil disse underlister blive sorteret ved hjælp af indsættelsessortering, hvor en midlertidig variabel bruges til at sammenligne både tal og sortere i overensstemmelse hermed.

Arrayet ville se sådan ud efter swapping operationer-

Trin 4) Nu vil vi mindske startværdien af ​​intervallet. Det nye interval vil være h=h/2 eller 4/2 eller 2.

Trin 5) Som 2>0 vil vi gå til trin 2 for at gemme alle elementer i en afstand på 2. For denne gang er underlisterne-

{1, 5, 8, 7}, {4, 2, 6, 3}

Derefter sorteres disse underlister ved hjælp af indsættelsessortering. Efter sammenligning og ombytningping den første underliste, ville arrayet være følgende.

Efter sortering af den anden underliste vil det originale array være:

Så igen vil intervallet blive reduceret. Nu vil intervallet være h=h/2 eller 2/1 eller 1. Derfor vil vi bruge indsættelsessorteringsalgoritmen til at sortere det modificerede array.

Følgende er den trinvise proceduremæssige afbildning af indsættelsessort.

Intervallet divideres igen med 2. På dette tidspunkt bliver intervallet 0. Så vi går til trin 6.

Trin 6) Da intervallet er 0, er arrayet sorteret efter dette tidspunkt. Det sorterede array er-

pseudoCode

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++

Input:

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

Output:

Sorted Output:

1 2 3 4 5 6 7 8

Shell Sortering Eksempel i Python

Input:

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

Output:

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

Anvendelser af Shell Sort

Her er vigtige anvendelser af Shell Sort:

• Skalsortering bruges i Linux-kernen fordi den ikke bruger en opkaldsstak.
• uClibc-biblioteket bruger Shell-sortering.
• bzip2-kompressor bruger Shell-sortering til at stoppe overskridelse af rekursion.

Fordele og ulemper ved Shell Sort

Fordele	Ulemper
Intet stackkald er påkrævet.	Ikke effektiv til store matrixstørrelser.
Nem implementering.	Ineffektiv til vidt udbredte elementer.
Effektiv til elementer med mindre afstand.

Shell Sort kompleksitetsanalyse

Tidskompleksitet af Shell-sortering

Tidskompleksiteten af ​​skalsorteringsalgoritmen er O(n^2). Begrundelsen er som følger:

For det bedste tilfælde er den samlede mængde af tests for alle intervaller, når arrayet tidligere var arrangeret lig med log n. Således ville kompleksiteten være O(n*log n).

For det værst tænkelige scenarie, lad os overveje, at arrayet består på en sådan måde, at elementerne kræver det højeste antal sammenligninger. Så vil alle elementer ikke blive sammenlignet og ændret før den sidste iteration. Derfor er de samlede sammenligninger, der kræves for den endelige stigning, O(n^2).

Afslutningsvis ville tidskompleksiteten være

1. Bedste sagskompleksitet: O(n*log n)
2. Gennemsnitlig sagskompleksitet: O(n*log n)
3. Værste tilfælde kompleksitet: O(n^2)

Køretidskompleksiteten af ​​shell-sortering afhænger i høj grad af de anvendte gap-inkrementersekvenser. Den bedste trinsekvens for skalsortering er dog stadig ukendt.

Shell Sort Space kompleksitet

I denne sammenligningstype har vi ikke brug for yderligere ekstra plads. Rumkompleksiteten af ​​denne slags algoritme er således O(1).