Dans cet article, nous discuterons de l’algorithme de tri shell. Le tri Shell est la généralisation du tri par insertion, qui pallie les inconvénients du tri par insertion en comparant des éléments séparés par un espace de plusieurs positions.
Il s'agit d'un algorithme de tri qui est une version étendue du tri par insertion. Le tri Shell a amélioré la complexité temporelle moyenne du tri par insertion. Tout comme le tri par insertion, il s'agit d'un algorithme de tri basé sur une comparaison et sur place. Le tri Shell est efficace pour les ensembles de données de taille moyenne.
Dans le tri par insertion, les éléments à la fois ne peuvent être avancés que d'une seule position. Pour déplacer un élément vers une position éloignée, de nombreux mouvements sont nécessaires qui augmentent le temps d'exécution de l'algorithme. Mais le tri shell surmonte cet inconvénient du tri par insertion. Il permet également le mouvement et l’échange d’éléments éloignés.
Cet algorithme trie d’abord les éléments éloignés les uns des autres, puis réduit ensuite l’écart entre eux. Cet écart est appelé intervalle. Cet intervalle peut être calculé en utilisant la Knuth formule donnée ci-dessous -
h = h * 3 + 1 where, 'h' is the interval having initial value 1.
Voyons maintenant l'algorithme de tri du shell.
Algorithme
Les étapes simples pour réaliser le tri des shells sont répertoriées comme suit :
tutoriel Java
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;>
Fonctionnement de l'algorithme de tri Shell
Voyons maintenant le fonctionnement de l'algorithme de tri shell.
Pour comprendre le fonctionnement de l'algorithme de tri du shell, prenons un tableau non trié. Il sera plus facile de comprendre le tri shell via un exemple.
Soit les éléments du tableau -
types de données SQL
Nous utiliserons la séquence originale de tri shell, c'est-à-dire N/2, N/4,....,1 comme intervalles.
Dans la première boucle, n est égal à 8 (taille du tableau), donc les éléments sont espacés de 4 (n/2 = 4). Les éléments seront comparés et échangés s’ils ne sont pas dans l’ordre.
Ici, dans la première boucle, l'élément au 0èmela position sera comparée à l'élément en 4èmeposition. Si le 0èmel'élément est plus grand, il sera échangé avec l'élément à 4èmeposition. Sinon, ça reste pareil. Ce processus se poursuivra pour les éléments restants.
A l'intervalle de 4, les sous-listes sont {33, 12}, {31, 17}, {40, 25}, {8, 42}.
Maintenant, nous devons comparer les valeurs de chaque sous-liste. Après comparaison, nous devons les échanger si nécessaire dans le tableau d'origine. Après comparaison et échange, le tableau mis à jour ressemblera à ceci :
Dans la deuxième boucle, les éléments se situent à un intervalle de 2 (n/4 = 2), où n = 8.
Maintenant, nous prenons l'intervalle de 2 pour trier le reste du tableau. Avec un intervalle de 2, deux sous-listes seront générées : {12, 25, 33, 40} et {17, 8, 31, 42}.
gigaoctet contre mégaoctet
Maintenant, nous devons à nouveau comparer les valeurs de chaque sous-liste. Après comparaison, nous devons les échanger si nécessaire dans le tableau d'origine. Après comparaison et échange, le tableau mis à jour ressemblera à ceci :
Dans la troisième boucle, les éléments se situent à l'intervalle de 1 (n/8 = 1), où n = 8. Enfin, nous utilisons l'intervalle de valeur 1 pour trier le reste des éléments du tableau. Dans cette étape, le tri shell utilise le tri par insertion pour trier les éléments du tableau.
Désormais, le tableau est trié par ordre croissant.
Complexité du tri Shell
Voyons maintenant la complexité temporelle du tri Shell dans le meilleur des cas, le cas moyen et le pire des cas. Nous verrons également la complexité spatiale du type Shell.
1. Complexité temporelle
| Cas | Complexité temporelle |
|---|---|
| Meilleur cas | O(n*logn) |
| Cas moyen | O(n*log(n)2) |
| Pire cas | Sur2) |
2. Complexité spatiale
| Complexité spatiale | O(1) |
| Écurie | NON |
- La complexité spatiale du tri Shell est O(1).
Implémentation du tri Shell
Voyons maintenant les programmes de Shell triés dans différents langages de programmation.
Programme: Écrivez un programme pour implémenter le tri Shell en langage 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;>