In questo articolo discuteremo dell'algoritmo di ordinamento della shell. Lo shell sort è la generalizzazione dell'insertion sort, che supera gli inconvenienti dell'insertion sort confrontando elementi separati da uno spazio di diverse posizioni.
È un algoritmo di ordinamento che è una versione estesa dell'ordinamento per inserzione. L'ordinamento della shell ha migliorato la complessità temporale media dell'ordinamento per inserimento. Simile all'ordinamento per inserzione, è un algoritmo di ordinamento basato sul confronto e sul posto. L'ordinamento della shell è efficiente per set di dati di medie dimensioni.
Nell'ordinamento per inserzione, gli elementi alla volta possono essere spostati avanti di una sola posizione. Per spostare un elemento in una posizione lontana sono necessari molti movimenti che aumentano il tempo di esecuzione dell'algoritmo. Ma l'ordinamento della shell supera questo inconveniente dell'ordinamento per inserzione. Permette il movimento e lo scambio anche di elementi lontani.
Questo algoritmo ordina prima gli elementi distanti tra loro, poi riduce successivamente il divario tra loro. Questo divario è chiamato come intervallo. Questo intervallo può essere calcolato utilizzando il Quello di Knuth formula indicata di seguito -
q2 mesi
h = h * 3 + 1 where, 'h' is the interval having initial value 1.
Ora vediamo l'algoritmo di shell sort.
Algoritmo
I semplici passaggi per ottenere l'ordinamento della shell sono elencati come segue:
Java concatena stringhe
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;>
Funzionamento dell'algoritmo di ordinamento di Shell
Ora vediamo il funzionamento dell'algoritmo di ordinamento della shell.
Per comprendere il funzionamento dell'algoritmo di ordinamento della shell, prendiamo un array non ordinato. Sarà più semplice comprendere l'ordinamento della shell tramite un esempio.
Lascia che gli elementi dell'array siano -
Utilizzeremo la sequenza originale dello shell sort, cioè N/2, N/4,....,1 come intervalli.
Nel primo ciclo n è uguale a 8 (dimensione dell'array), quindi gli elementi si trovano nell'intervallo 4 (n/2 = 4). Gli elementi verranno confrontati e scambiati se non sono in ordine.
Qui, nel primo ciclo, l'elemento allo 0thla posizione verrà confrontata con l'elemento in 4thposizione. Se lo 0thl'elemento è maggiore, verrà scambiato con l'elemento 4thposizione. Altrimenti rimane lo stesso. Questo processo continuerà per i restanti elementi.
Nell'intervallo 4 le sottoliste sono {33, 12}, {31, 17}, {40, 25}, {8, 42}.
Ora dobbiamo confrontare i valori in ogni sottoelenco. Dopo il confronto, dobbiamo scambiarli, se necessario, nell'array originale. Dopo il confronto e lo scambio, l'array aggiornato apparirà come segue:
Nel secondo ciclo gli elementi si trovano nell'intervallo 2 (n/4 = 2), dove n = 8.
convertire la stringa in numero intero
Ora stiamo prendendo l'intervallo di 2 per ordinare il resto dell'array. Con un intervallo di 2, verranno generate due sottoliste: {12, 25, 33, 40} e {17, 8, 31, 42}.
Ora dobbiamo confrontare nuovamente i valori in ogni sottoelenco. Dopo il confronto, dobbiamo scambiarli, se necessario, nell'array originale. Dopo il confronto e lo scambio, l'array aggiornato apparirà come segue:
cos'è un hashset in Java
Nel terzo ciclo, gli elementi si trovano nell'intervallo 1 (n/8 = 1), dove n = 8. Infine, utilizziamo l'intervallo di valore 1 per ordinare il resto degli elementi dell'array. In questo passaggio, l'ordinamento della shell utilizza l'ordinamento per inserimento per ordinare gli elementi dell'array.
Ora l'array è ordinato in ordine crescente.
Complessità dell'ordinamento della shell
Ora, vediamo la complessità temporale dell'ordinamento di Shell nel caso migliore, nel caso medio e nel caso peggiore. Vedremo anche la complessità spaziale dello Shell sort.
1. Complessità temporale
| Caso | Complessità temporale |
|---|---|
| Caso migliore | O(n*log) |
| Caso medio | O(n*log(n)2) |
| Caso peggiore | SU2) |
2. Complessità spaziale
| Complessità spaziale | O(1) |
| Stabile | NO |
- La complessità spaziale dello Shell sort è O(1).
Implementazione dell'ordinamento Shell
Vediamo ora i programmi della Shell ordinati nei diversi linguaggi di programmazione.
Programma: Scrivere un programma per implementare l'ordinamento della shell in linguaggio 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;>