En aquest article, parlarem de l'algorisme d'ordenació de l'intèrpret d'ordres. L'ordenació de shell és la generalització de l'ordenació d'inserció, que supera els inconvenients de l'ordenació d'inserció comparant elements separats per un buit de diverses posicions.
És un algorisme d'ordenació que és una versió ampliada de l'ordenació per inserció. L'ordenació de shell ha millorat la complexitat del temps mitjà de l'ordenació d'inserció. Igual que l'ordenació per inserció, és un algorisme d'ordenació basat en comparacions i al lloc. L'ordenació de shell és eficient per a conjunts de dades de mida mitjana.
tostring java
En l'ordenació per inserció, a la vegada, els elements es poden moure cap endavant només per una posició. Per moure un element a una posició llunyana, calen molts moviments que augmenten el temps d'execució de l'algorisme. Però l'ordenació de shell supera aquest inconvenient de l'ordenació d'inserció. També permet el moviment i l'intercanvi d'elements llunyans.
Aquest algorisme ordena primer els elements que estan lluny els uns dels altres i, posteriorment, redueix la bretxa entre ells. Aquest buit s'anomena com interval. Aquest interval es pot calcular utilitzant el de Knuth fórmula que es mostra a continuació -
h = h * 3 + 1 where, 'h' is the interval having initial value 1.
Ara, anem a veure l'algoritme d'ordenació de shell.
Algorisme
Els passos senzills per aconseguir l'ordenació de shell s'enumeren de la següent manera:
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;>
Funcionament de l'algoritme d'ordenació de Shell
Ara, vegem el funcionament de l'algoritme d'ordenació de l'intèrpret d'ordres.
Per entendre el funcionament de l'algorisme d'ordenació de l'intèrpret d'ordres, prenem una matriu sense ordenar. Serà més fàcil entendre l'ordenació de l'intèrpret d'ordres mitjançant un exemple.
Siguin els elements de la matriu -
Utilitzarem la seqüència original d'ordenació de shell, és a dir, N/2, N/4,....,1 com a intervals.
En el primer bucle, n és igual a 8 (mida de la matriu), de manera que els elements es troben a l'interval de 4 (n/2 = 4). Els elements es compararan i s'intercanviaran si no estan en ordre.
Aquí, en el primer bucle, l'element al 0thla posició es compararà amb l'element a 4thposició. Si el 0thelement és més gran, s'intercanviarà amb l'element a 4thposició. En cas contrari, segueix sent igual. Aquest procés continuarà per als elements restants.
els 10 millors hentai
A l'interval de 4, les subllistes són {33, 12}, {31, 17}, {40, 25}, {8, 42}.
Ara, hem de comparar els valors de cada subllista. Després de comparar, hem d'intercanviar-los si és necessari a la matriu original. Després de comparar i intercanviar, la matriu actualitzada tindrà el següent aspecte:
En el segon bucle, els elements es troben a l'interval de 2 (n/4 = 2), on n = 8.
Ara, estem prenent l'interval de 2 per ordenar la resta de la matriu. Amb un interval de 2, es generaran dues subllistes: {12, 25, 33, 40} i {17, 8, 31, 42}.
Ara, hem de tornar a comparar els valors de cada subllista. Després de comparar, hem d'intercanviar-los si és necessari a la matriu original. Després de comparar i intercanviar, la matriu actualitzada tindrà el següent aspecte:
En el tercer bucle, els elements es troben a l'interval d'1 (n/8 = 1), on n = 8. Finalment, utilitzem l'interval de valor 1 per ordenar la resta d'elements de la matriu. En aquest pas, l'ordenació de shell utilitza l'ordenació d'inserció per ordenar els elements de la matriu.
Ara, la matriu s'ordena en ordre ascendent.
Complexitat d'ordenació de Shell
Ara, vegem la complexitat temporal de l'ordenació de Shell en el millor dels casos, el cas mitjà i el pitjor. També veurem la complexitat espacial del tipus Shell.
1. Complexitat temporal
| Caixa | Complexitat temporal |
|---|---|
| Millor cas | O(n*inici de sessió) |
| Cas mitjà | O(n*log(n)2) |
| Pitjor dels casos | O (n2) |
2. Complexitat espacial
| Complexitat espacial | O(1) |
| Estable | NO |
- La complexitat espacial de l'ordenació Shell és O(1).
Implementació del tipus Shell
Ara, vegem els programes de Shell ordenats en diferents llenguatges de programació.
Programa: Escriu un programa per implementar l'ordenació de Shell en llenguatge 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;>