I denne artikel vil vi diskutere shell-sorteringsalgoritmen. Skalsortering er generaliseringen af ​​indsættelsessortering, som overvinder ulemperne ved indsættelsessortering ved at sammenligne elementer adskilt af et mellemrum på flere positioner.

Det er en sorteringsalgoritme, der er en udvidet version af indsættelsessortering. Shell-sortering har forbedret den gennemsnitlige tidskompleksitet af indsættelsessortering. Ligesom indsættelsessortering er det en sammenligningsbaseret og på stedet sorteringsalgoritme. Skalsortering er effektiv til mellemstore datasæt.

Ved indsættelsessortering ad gangen kan elementer kun flyttes én position frem. For at flytte et element til en position langt væk, kræves der mange bevægelser, der øger algoritmens eksekveringstid. Men shell-sortering overvinder denne ulempe ved indsættelsessortering. Det tillader også bevægelse og udskiftning af fjerntliggende elementer.

Denne algoritme sorterer først de elementer, der er langt væk fra hinanden, og derefter reducerer den kløften mellem dem. Dette hul kaldes som interval. Dette interval kan beregnes ved at bruge Knuths formel givet nedenfor -

 h = h * 3 + 1 where, 'h' is the interval having initial value 1. 

Lad os nu se algoritmen for skalsortering.

Algoritme

De enkle trin til at opnå shell-sortering er angivet som følger -

 ShellSort(a, n) // &apos;a&apos; is the given array, &apos;n&apos; is the size of array for (interval = n/2; interval &gt; 0; interval /= 2) for ( i = interval; i <n; i +="1)" temp="a[i];" for (j="i;" j>= interval &amp;&amp; a[j - interval] &gt; temp; j -= interval) a[j] = a[j - interval]; a[j] = temp; End ShellSort </n;>

Arbejde med Shell-sortalgoritmen

Lad os nu se, hvordan shell-sorteringsalgoritmen fungerer.

For at forstå, hvordan shell-sorteringsalgoritmen fungerer, lad os tage et usorteret array. Det vil være lettere at forstå skalsorteringen via et eksempel.

Lad elementerne i array være -

Vi vil bruge den originale sekvens af skalsortering, dvs. N/2, N/4,....,1 som intervallerne.

I den første sløjfe er n lig med 8 (størrelsen af ​​arrayet), så elementerne ligger i intervallet 4 (n/2 = 4). Elementer vil blive sammenlignet og byttet, hvis de ikke er i orden.

Her, i den første sløjfe, er elementet ved 0^thposition vil blive sammenlignet med elementet ved 4^thposition. Hvis 0^thelementet er større, vil det blive byttet med elementet ved 4^thposition. Ellers forbliver det det samme. Denne proces vil fortsætte for de resterende elementer.

I intervallet 4 er underlisterne {33, 12}, {31, 17}, {40, 25}, {8, 42}.

Nu skal vi sammenligne værdierne i hver underliste. Efter at have sammenlignet, er vi nødt til at bytte dem, hvis det kræves i det originale array. Efter sammenligning og ombytning vil det opdaterede array se ud som følger -

I den anden sløjfe ligger elementerne i intervallet 2 (n/4 = 2), hvor n = 8.

Nu tager vi intervallet af 2 for at sortere resten af ​​arrayet. Med et interval på 2 vil der blive genereret to underlister - {12, 25, 33, 40} og {17, 8, 31, 42}.

Nu skal vi igen sammenligne værdierne i hver underliste. Efter at have sammenlignet, er vi nødt til at bytte dem, hvis det kræves i det originale array. Efter sammenligning og ombytning vil det opdaterede array se ud som følger -

I den tredje sløjfe ligger elementer i intervallet 1 (n/8 = 1), hvor n = 8. Til sidst bruger vi intervallet med værdi 1 til at sortere resten af ​​array-elementerne. I dette trin bruger shell-sortering indsættelsessortering til at sortere array-elementerne.

Nu er arrayet sorteret i stigende rækkefølge.

Skalsorteringskompleksitet

Lad os nu se tidskompleksiteten af ​​Shell-sortering i bedste tilfælde, gennemsnitligt tilfælde og værste tilfælde. Vi vil også se rumkompleksiteten af ​​Shell-sorten.

1. Tidskompleksitet

Best case kompleksitet -Det opstår, når der ikke er behov for sortering, dvs. arrayet er allerede sorteret. Den bedst mulige tidskompleksitet af Shell-sortering er O(n*logn). Gennemsnitlig sagskompleksitet -Det opstår, når array-elementerne er i rodet rækkefølge, der ikke er korrekt stigende og ikke korrekt faldende. Den gennemsnitlige sagstidskompleksitet af Shell-sortering er O(n*logn). Worst Case Complexity -Det opstår, når array-elementerne skal sorteres i omvendt rækkefølge. Det betyder, at du skal sortere array-elementerne i stigende rækkefølge, men dets elementer er i faldende rækkefølge. Det værst tænkelige tidskompleksitet af Shell-sort er På²).

2. Rumkompleksitet

• Rumkompleksiteten af ​​Shell-sortering er O(1).

Implementering af Shell sort

Lad os nu se Shells programmer sortere på forskellige programmeringssprog.

Program: Skriv et program til at implementere Shell-sortering i C-sprog.

 #include /* function to implement shellSort */ int shell(int a[], int n) { /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */ for (int interval = n/2; interval &gt; 0; interval /= 2) { for (int i = interval; i <n; i +="1)" { * store a[i] to the variable temp and make ith position empty int j; for (j="i;" j>= interval &amp;&amp; a[j - interval] &gt; temp; j -= interval) a[j] = a[j - interval]; // put temp (the original a[i]) in its correct position a[j] = temp; } } return 0; } void printArr(int a[], int n) /* function to print the array elements */ { int i; for (i = 0; i <n; 42 i++) printf('%d ', a[i]); } int main() { a[]="{" 33, 31, 40, 8, 12, 17, 25, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are - 
'); printarr(a, n); shell(a, printf('
after applying shell sort, the return 0; < pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/72/shell-sort-algorithm-7.webp" alt="Shell Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Shell sort in C++.</p> <pre> #include using namespace std; /* function to implement shellSort */ int shell(int a[], int n) { /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */ for (int interval = n/2; interval &gt; 0; interval /= 2) { for (int i = interval; i <n; i +="1)" { * store a[i] to the variable temp and make ith position empty int j; for (j="i;" j>= interval &amp;&amp; a[j - interval] &gt; temp; j -= interval) a[j] = a[j - interval]; // put temp (the original a[i]) in its correct position a[j] = temp; } } return 0; } void printArr(int a[], int n) /* function to print the array elements */ { int i; for (i = 0; i <n; 41 i++) cout< <a[i]<<' '; } int main() { a[]="{" 32, 30, 39, 7, 11, 16, 24, }; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are - 
'; printarr(a, n); shell(a, cout<<'
after applying shell sort, the return 0; < pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/72/shell-sort-algorithm-8.webp" alt="Shell Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Shell sort in C#.</p> <pre> using System; class ShellSort { /* function to implement shellSort */ static void shell(int[] a, int n) { /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */ for (int interval = n/2; interval &gt; 0; interval /= 2) { for (int i = interval; i <n; i +="1)" { * store a[i] to the variable temp and make ith position empty int j; for (j="i;" j>= interval &amp;&amp; a[j - interval] &gt; temp; j -= interval) a[j] = a[j - interval]; /* put temp (the original a[i]) in its correct position */ a[j] = temp; } } } static void printArr(int[] a, int n) /* function to print the array elements */ { int i; for (i = 0; i <n; 40 i++) console.write(a[i] + ' '); } static void main() { int[] a="{" 31, 29, 38, 6, 10, 15, 23, }; int n="a.Length;" console.write('before sorting array elements are - 
'); printarr(a, n); shell(a, console.write('
after applying shell sort, the < pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/72/shell-sort-algorithm-9.webp" alt="Shell Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Shell sort in Java.</p> <pre> class ShellSort { /* function to implement shellSort */ static void shell(int a[], int n) { /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */ for (int interval = n/2; interval &gt; 0; interval /= 2) { for (int i = interval; i <n; i +="1)" { * store a[i] to the variable temp and make ith position empty int j; for (j="i;" j>= interval &amp;&amp; a[j - interval] &gt; temp; j -= interval) a[j] = a[j - interval]; /* put temp (the original a[i]) in its correct position */ a[j] = temp; } } } static void printArr(int a[], int n) /* function to print the array elements */ { int i; for (i = 0; i <n; 39 i++) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{" 30, 28, 37, 5, 9, 14, 22, }; n="a.length;" system.out.print('before sorting array elements are - 
'); printarr(a, n); shell(a, system.out.print('
after applying shell sort, the < pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/72/shell-sort-algorithm-10.webp" alt="Shell Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></n;></pre></n;></n;></pre></n;></n;></pre></n;></n;>