I den här artikeln kommer vi att diskutera skalsorteringsalgoritmen. Skalsortering är generaliseringen av infogningssortering, som övervinner nackdelarna med infogningssortering genom att jämföra element åtskilda av ett mellanrum med flera positioner.
Det är en sorteringsalgoritm som är en utökad version av infogningssortering. Skalsortering har förbättrat den genomsnittliga tidskomplexiteten för infogningssortering. Liksom insättningssortering är det en jämförelsebaserad och på plats sorteringsalgoritm. Skalsortering är effektivt för medelstora datamängder.
Vid insättningssortering kan element åt gången flyttas framåt med endast en position. För att flytta ett element till en långt borta position krävs många rörelser som ökar algoritmens exekveringstid. Men skalsortering övervinner denna nackdel med infogningssort. Det tillåter rörelse och byte av element på långt håll också.
Denna algoritm sorterar först de element som är långt borta från varandra, sedan minskar den sedan gapet mellan dem. Denna lucka kallas som intervall. Detta intervall kan beräknas med hjälp av Knuths formeln nedan -
h = h * 3 + 1 where, 'h' is the interval having initial value 1.
Låt oss nu se algoritmen för skalsortering.
Algoritm
De enkla stegen för att uppnå skalsortering listas enligt följande -
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;>
Arbetar med Shell-sortalgoritm
Låt oss nu se hur skalsorteringsalgoritmen fungerar.
För att förstå hur skalsorteringsalgoritmen fungerar, låt oss ta en osorterad array. Det blir lättare att förstå skalsorteringen via ett exempel.
Låt elementen i arrayen vara -
Vi kommer att använda den ursprungliga sekvensen av skalsortering, dvs N/2, N/4,....,1 som intervall.
I den första slingan är n lika med 8 (matrisens storlek), så elementen ligger i intervallet 4 (n/2 = 4). Element kommer att jämföras och bytas ut om de inte är i ordning.
Här, i den första slingan, elementet vid 0thposition kommer att jämföras med elementet vid 4thplacera. Om 0thelementet är större, kommer det att bytas ut mot elementet vid 4thplacera. Annars förblir det detsamma. Denna process kommer att fortsätta för de återstående delarna.
Vid intervallet 4 är underlistorna {33, 12}, {31, 17}, {40, 25}, {8, 42}.
Nu måste vi jämföra värdena i varje underlista. Efter jämförelse måste vi byta ut dem om det behövs i den ursprungliga arrayen. Efter jämförelse och byte kommer den uppdaterade arrayen att se ut som följer -
I den andra slingan ligger elementen i intervallet 2 (n/4 = 2), där n = 8.
Nu tar vi intervallet av 2 för att sortera resten av arrayen. Med ett intervall på 2 kommer två underlistor att genereras - {12, 25, 33, 40} och {17, 8, 31, 42}.
Nu måste vi återigen jämföra värdena i varje underlista. Efter jämförelse måste vi byta ut dem om det behövs i den ursprungliga arrayen. Efter jämförelse och byte kommer den uppdaterade arrayen att se ut som följer -
I den tredje slingan ligger element i intervallet 1 (n/8 = 1), där n = 8. Till sist använder vi intervallet för värde 1 för att sortera resten av arrayelementen. I det här steget använder skalsortering insättningssortering för att sortera arrayelementen.
Nu är matrisen sorterad i stigande ordning.
Skalsorteringskomplexitet
Låt oss nu se tidskomplexiteten hos Shell-sorteringen i bästa fall, genomsnittligt fall och värsta fall. Vi kommer också att se rymdkomplexiteten hos Shell-sorten.
1. Tidskomplexitet
| Fall | Tidskomplexitet |
|---|---|
| Bästa fall | O(n*logn) |
| Genomsnittligt fall | O(n*log(n)2) |
| Värsta fall | På2) |
2. Rymdkomplexitet
| Rymdkomplexitet | O(1) |
| Stabil | NEJ |
- Utrymmeskomplexiteten för Shell-sorteringen är O(1).
Implementering av Shell sort
Låt oss nu se Shells program sortera i olika programmeringsspråk.
Program: Skriv ett program för att implementera 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;>