In dit artikel bespreken we het shell-sorteeralgoritme. Shell-soort is de generalisatie van invoeg-soort, die de nadelen van invoeg-soort overwint door elementen te vergelijken die gescheiden zijn door een opening van verschillende posities.
Het is een sorteeralgoritme dat een uitgebreide versie is van invoegsortering. Shell-sortering heeft de gemiddelde tijdcomplexiteit van invoegsortering verbeterd. Net als bij invoegsortering is het een op vergelijkingen gebaseerd en ter plaatse sorteeralgoritme. Shell-sortering is efficiënt voor middelgrote datasets.
Bij invoegsortering kunnen elementen slechts één positie vooruit worden verplaatst. Om een element naar een verre positie te verplaatsen zijn veel bewegingen nodig die de uitvoeringstijd van het algoritme vergroten. Maar shell-sortering overwint dit nadeel van insertie-sortering. Het maakt ook het verplaatsen en verwisselen van verre elementen mogelijk.
Dit algoritme sorteert eerst de elementen die ver van elkaar verwijderd zijn, en verkleint vervolgens de kloof ertussen. Deze kloof wordt genoemd als interval. Dit interval kan worden berekend met behulp van de Knuth's onderstaande formule -
h = h * 3 + 1 where, 'h' is the interval having initial value 1.
Laten we nu eens kijken naar het algoritme van shell-sortering.
Algoritme
De eenvoudige stappen voor het bereiken van de shell-sortering worden als volgt weergegeven:
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;>
Werking van het Shell-soortalgoritme
Laten we nu eens kijken naar de werking van het shell-sorteeralgoritme.
Om de werking van het shell-sorteeralgoritme te begrijpen, nemen we een ongesorteerde array. Het zal gemakkelijker zijn om de shell-sortering te begrijpen aan de hand van een voorbeeld.
Laat de elementen van array zijn -
We zullen de originele volgorde van shell-sortering gebruiken, d.w.z. N/2, N/4,...,1 als de intervallen.
In de eerste lus is n gelijk aan 8 (grootte van de array), dus de elementen liggen op het interval van 4 (n/2 = 4). Elementen worden vergeleken en verwisseld als ze niet in orde zijn.
Hier, in de eerste lus, het element op 0epositie wordt vergeleken met het element op 4epositie. Als de 0eelement groter is, wordt het verwisseld met het element op 4epositie. Anders blijft het hetzelfde. Dit proces zal doorgaan voor de overige elementen.
Met een interval van 4 zijn de sublijsten {33, 12}, {31, 17}, {40, 25}, {8, 42}.
Nu moeten we de waarden in elke sublijst vergelijken. Na het vergelijken moeten we ze indien nodig in de originele array omwisselen. Na het vergelijken en omwisselen ziet de bijgewerkte array er als volgt uit:
In de tweede lus liggen de elementen op het interval van 2 (n/4 = 2), waarbij n = 8.
Nu nemen we het interval van 2 om de rest van de array te sorteren. Met een interval van 2 worden er twee sublijsten gegenereerd: {12, 25, 33, 40} en {17, 8, 31, 42}.
Nu moeten we opnieuw de waarden in elke sublijst vergelijken. Na het vergelijken moeten we ze indien nodig in de originele array omwisselen. Na het vergelijken en omwisselen ziet de bijgewerkte array er als volgt uit:
In de derde lus liggen de elementen op het interval van 1 (n/8 = 1), waarbij n = 8. Ten slotte gebruiken we het interval van waarde 1 om de rest van de array-elementen te sorteren. In deze stap gebruikt shell-sortering invoegsortering om de array-elementen te sorteren.
Nu wordt de array in oplopende volgorde gesorteerd.
Complexiteit van shell-sortering
Laten we nu eens kijken naar de tijdscomplexiteit van Shell, in het beste geval, het gemiddelde geval en het slechtste geval. We zullen ook de ruimtecomplexiteit van het Shell-type zien.
1. Tijdcomplexiteit
| Geval | Tijdcomplexiteit |
|---|---|
| Beste geval | O(n*loggen) |
| Gemiddeld geval | O(n*log(n)2) |
| Het slechtste geval | Op2) |
2. Ruimtecomplexiteit
| Ruimtecomplexiteit | O(1) |
| Stal | NEE |
- De ruimtecomplexiteit van Shell-soort is O(1).
Implementatie van Shell-soort
Laten we nu eens kijken hoe de programma's van Shell in verschillende programmeertalen worden gesorteerd.
Programma: Schrijf een programma om Shell sort in C-taal te implementeren.
#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;>