În acest articol, vom discuta despre algoritmul de sortare shell. Sortarea shell este generalizarea sortării prin inserție, care depășește dezavantajele sortării prin inserție prin compararea elementelor separate printr-un interval de mai multe poziții.
Este un algoritm de sortare care este o versiune extinsă a sortării prin inserție. Sortarea Shell a îmbunătățit complexitatea timpului mediu al sortării prin inserare. Asemănător cu sortarea prin inserție, este un algoritm de sortare pe loc și bazat pe comparație. Sortarea Shell este eficientă pentru seturi de date de dimensiuni medii.
În sortarea prin inserare, la un moment dat, elementele pot fi mutate înainte doar cu o singură poziție. Pentru a muta un element într-o poziție îndepărtată, sunt necesare multe mișcări care măresc timpul de execuție al algoritmului. Dar sortarea shell depășește acest dezavantaj al sortării prin inserție. Permite mișcarea și schimbarea elementelor îndepărtate.
Acest algoritm sortează mai întâi elementele care sunt departe unele de altele, apoi reduce decalajul dintre ele. Acest decalaj se numește ca interval. Acest interval poate fi calculat utilizând a lui Knuth formula prezentată mai jos -
h = h * 3 + 1 where, 'h' is the interval having initial value 1.
Acum, să vedem algoritmul de sortare shell.
Algoritm
Pașii simpli pentru realizarea sortării shell sunt enumerați după cum urmează -
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;>
Funcționarea algoritmului de sortare Shell
Acum, să vedem funcționarea algoritmului de sortare a shell-ului.
convertiți int în șir de caractere java
Pentru a înțelege funcționarea algoritmului de sortare shell, să luăm o matrice nesortată. Va fi mai ușor de înțeles sortarea shell-ului printr-un exemplu.
Fie elementele matricei sunt -
Vom folosi secvența originală de sortare shell, adică N/2, N/4,....,1 ca intervale.
convertiți data șirului
În prima buclă, n este egal cu 8 (dimensiunea matricei), deci elementele se află la intervalul de 4 (n/2 = 4). Elementele vor fi comparate și schimbate dacă nu sunt în ordine.
Aici, în prima buclă, elementul la 0thpoziția va fi comparată cu elementul de la 4thpoziţie. Dacă 0thelementul este mai mare, va fi schimbat cu elementul la 4thpoziţie. În rest, rămâne la fel. Acest proces va continua pentru elementele rămase.
La intervalul de 4, sublistele sunt {33, 12}, {31, 17}, {40, 25}, {8, 42}.
Acum, trebuie să comparăm valorile din fiecare sub-listă. După comparare, trebuie să le schimbăm dacă este necesar în matricea originală. După comparare și schimbare, matricea actualizată va arăta după cum urmează -
În a doua buclă, elementele se află la intervalul de 2 (n/4 = 2), unde n = 8.
Acum, luăm intervalul de 2 pentru a sorta restul matricei. Cu un interval de 2, vor fi generate două subliste - {12, 25, 33, 40} și {17, 8, 31, 42}.
converti șirul în întreg
Acum, trebuie din nou să comparăm valorile din fiecare sub-listă. După comparare, trebuie să le schimbăm dacă este necesar în matricea originală. După comparare și schimbare, matricea actualizată va arăta după cum urmează -
În a treia buclă, elementele se află la intervalul de 1 (n/8 = 1), unde n = 8. În cele din urmă, folosim intervalul de valoare 1 pentru a sorta restul elementelor matricei. În acest pas, sortarea shell folosește sortarea prin inserție pentru a sorta elementele matricei.
Acum, matricea este sortată în ordine crescătoare.
Complexitatea sortării Shell
Acum, să vedem complexitatea temporală a sortării Shell în cel mai bun caz, caz mediu și cel mai rău caz. Vom vedea, de asemenea, complexitatea spațială a tipului Shell.
1. Complexitatea timpului
| Caz | Complexitatea timpului |
|---|---|
| Cel mai bun caz | O(n*logn) |
| Caz mediu | O(n*log(n)2) |
| Cel mai rău caz | Pe2) |
2. Complexitatea spațială
| Complexitatea spațială | O(1) |
| Grajd | NU |
- Complexitatea spațială a sortării Shell este O(1).
Implementarea sortării Shell
Acum, să vedem programele de sortare Shell în diferite limbaje de programare.
Program: Scrieți un program pentru a implementa sortarea Shell în limbajul C.
#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;>