Structure des données et algorithmes - Tri Shell

Le tri par shell est un algorithme de tri très efficace basé sur un algorithme de tri par insertion. Cet algorithme évite les grands décalages comme dans le cas du tri par insertion, si la valeur la plus petite est à l'extrême droite et doit être déplacée vers l'extrême gauche.

Cet algorithme utilise le tri par insertion sur des éléments largement répandus, d'abord pour les trier, puis trie les éléments les moins espacés. Cet espacement est appeléinterval. Cet intervalle est calculé sur la base de la formule de Knuth comme -

Formule de Knuth

h = h * 3 + 1
where −
   h is interval with initial value 1

Cet algorithme est assez efficace pour les ensembles de données de taille moyenne car sa complexité moyenne et dans le pire des cas de cet algorithme dépend de la séquence de brèches la plus connue est Ο (n), où n est le nombre d'éléments. Et le pire des cas de complexité spatiale est O (n).

Comment fonctionne Shell Sort?

Prenons l'exemple suivant pour avoir une idée du fonctionnement du tri shell. Nous prenons le même tableau que nous avons utilisé dans nos exemples précédents. Pour notre exemple et la facilité de compréhension, nous prenons l'intervalle de 4. Faites une sous-liste virtuelle de toutes les valeurs situées à l'intervalle de 4 positions. Ici, ces valeurs sont {35, 14}, {33, 19}, {42, 27} et {10, 44}

Nous comparons les valeurs de chaque sous-liste et les échangeons (si nécessaire) dans le tableau d'origine. Après cette étape, le nouveau tableau devrait ressembler à ceci -

Ensuite, nous prenons un intervalle de 1 et cet écart génère deux sous-listes - {14, 27, 35, 42}, {19, 10, 33, 44}

Nous comparons et échangeons les valeurs, si nécessaire, dans le tableau d'origine. Après cette étape, le tableau devrait ressembler à ceci -

Enfin, nous trions le reste du tableau en utilisant l'intervalle de valeur 1. Le tri shell utilise le tri par insertion pour trier le tableau.

Voici la représentation étape par étape -

Nous voyons qu'il n'a fallu que quatre swaps pour trier le reste du tableau.

Algorithme

Voici l'algorithme de tri par shell.

Step 1 − Initialize the value of h
Step 2 − Divide the list into smaller sub-list of equal interval h
Step 3 − Sort these sub-lists using insertion sort
Step 3 − Repeat until complete list is sorted

Pseudocode

Voici le pseudocode pour le tri shell.

procedure shellSort()
   A : array of items 
	
   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 + 1	    
   end while
   
   while interval > 0 do:

      for outer = interval; outer < A.length; outer ++ do:

      /* select value to be inserted */
      valueToInsert = A[outer]
      inner = outer;

         /*shift element towards right*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner - interval]
            inner = inner - interval
         end while

      /* insert the number at hole position */
      A[inner] = valueToInsert

      end for

   /* calculate interval*/
   interval = (interval -1) /3;	  

   end while
   
end procedure

Pour connaître l'implémentation du tri shell dans le langage de programmation C, veuillez cliquer ici .