I denne artikkelen vil vi diskutere skallsorteringsalgoritmen. Skallsortering er generaliseringen av innsettingssortering, som overvinner ulempene med innsettingssortering ved å sammenligne elementer atskilt med et gap på flere posisjoner.
Det er en sorteringsalgoritme som er en utvidet versjon av innsettingssortering. Shell-sortering har forbedret den gjennomsnittlige tidskompleksiteten for innsettingssortering. Som lik innsettingssortering er det en sammenligningsbasert og på plass sorteringsalgoritme. Skallsortering er effektiv for mellomstore datasett.
Ved innsettingssortering, om gangen, kan elementer flyttes frem med kun én posisjon. For å flytte et element til en posisjon langt unna, kreves det mange bevegelser som øker algoritmens utførelsestid. Men skallsortering overvinner denne ulempen med innsettingssortering. Den tillater bevegelse og bytting av fjerntliggende elementer også.
Denne algoritmen sorterer først elementene som er langt unna hverandre, og deretter reduserer den gapet mellom dem. Dette gapet kalles som intervall. Dette intervallet kan beregnes ved å bruke Knuth sin formel gitt nedenfor -
h = h * 3 + 1 where, 'h' is the interval having initial value 1.
La oss nå se algoritmen for skallsortering.
Algoritme
De enkle trinnene for å oppnå skallsortering er oppført som følger -
ShellSort(a, n) // 'a' is the given array, 'n' is the size of array for (interval = n/2; interval > 0; interval /= 2) for ( i = interval; i <n; i +="1)" temp="a[i];" for (j="i;" j>= interval && a[j - interval] > temp; j -= interval) a[j] = a[j - interval]; a[j] = temp; End ShellSort </n;>
Arbeider med Shell-sortalgoritmen
La oss nå se hvordan skjellsorteringsalgoritmen fungerer.
For å forstå hvordan skallsorteringsalgoritmen fungerer, la oss ta en usortert matrise. Det vil være lettere å forstå skallsorteringen via et eksempel.
La elementene i array være -
Vi vil bruke den opprinnelige sekvensen av skallsortering, dvs. N/2, N/4,....,1 som intervaller.
I den første sløyfen er n lik 8 (størrelsen på matrisen), så elementene ligger i intervallet 4 (n/2 = 4). Elementer vil bli sammenlignet og byttet hvis de ikke er i orden.
Her, i den første sløyfen, er elementet ved 0thposisjon vil bli sammenlignet med elementet ved 4thposisjon. Hvis 0thelementet er større, vil det bli byttet med elementet ved 4thposisjon. Ellers forblir det det samme. Denne prosessen vil fortsette for de resterende elementene.
Ved intervallet 4 er underlistene {33, 12}, {31, 17}, {40, 25}, {8, 42}.
Nå må vi sammenligne verdiene i hver underliste. Etter å ha sammenlignet, må vi bytte dem om nødvendig i den originale matrisen. Etter å ha sammenlignet og byttet, vil den oppdaterte matrisen se ut som følger -
I den andre sløyfen ligger elementene i intervallet 2 (n/4 = 2), hvor n = 8.
Nå tar vi intervallet på 2 for å sortere resten av matrisen. Med et intervall på 2 vil to underlister bli generert - {12, 25, 33, 40} og {17, 8, 31, 42}.
Nå må vi igjen sammenligne verdiene i hver underliste. Etter å ha sammenlignet, må vi bytte dem om nødvendig i den originale matrisen. Etter å ha sammenlignet og byttet, vil den oppdaterte matrisen se ut som følger -
I den tredje sløyfen ligger elementene i intervallet 1 (n/8 = 1), hvor n = 8. Til slutt bruker vi intervallet til verdi 1 for å sortere resten av matriseelementene. I dette trinnet bruker shell-sortering innsettingssortering for å sortere array-elementene.
Nå er matrisen sortert i stigende rekkefølge.
Shell sortere kompleksitet
La oss nå se tidskompleksiteten til Shell-sortering i beste tilfelle, gjennomsnittlig tilfelle og verste tilfelle. Vi vil også se romkompleksiteten til Shell-sorten.
1. Tidskompleksitet
| Sak | Tidskompleksitet |
|---|---|
| Beste sak | O(n*logn) |
| Gjennomsnittlig sak | O(n*log(n)2) |
| Worst Case | På2) |
2. Romkompleksitet
| Plass kompleksitet | O(1) |
| Stabil | NEI |
- Romkompleksiteten til Shell-sortering er O(1).
Implementering av Shell sort
La oss nå se programmene til Shell sortere på forskjellige programmeringsspråk.
Program: Skriv et program for å implementere Shell-sortering i C-språk.
#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 > 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 && a[j - interval] > 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 > 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 && a[j - interval] > 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 > 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 && a[j - interval] > 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 > 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 && a[j - interval] > 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'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;>