Algorithme de tri Shell avec EXEMPLE

Qu'est-ce que le tri par coque

La méthode Shell, ou tri Shell dans la structure de données, est un algorithme de tri par comparaison sur place efficace. Il porte le nom de Donald Shell lorsqu'il a proposé l'idée initiale en 1959. Le tri Shell est une extension généralisée de l'algorithme de tri par insertion.

L’idée fondamentale de cet algorithme de tri est de regrouper les éléments éloignés les uns des autres et de les trier en conséquence. Puis diminuez progressivement l’écart entre eux. Le tri par shell surmonte le temps de traitement moyenplexité du tri par insertion en comparant et en échangeant des éléments éloignés.

Cet écart, appelé intervalle, est réduit selon certaines séquences d'intervalles optimales. Le temps d'exécution du tri shell dépend également de ces séquences. Il existe plusieurs séquences d'espacement, telles que la séquence originale de Shell, la formule de Knuth, les incréments de Hibbard, etc. La séquence d'espacement originale de Shell est - n/2, n/4, n/8, ……….1

Algorithme de tri des coques

Les étapes ou la procédure de l'algorithme de tri du shell sont les suivantes :

Étape 1) Initialisez la valeur de l'intervalle, h = n/2. (Dans cet exemple, n est la taille du tableau)

Étape 2) Mettez tous les éléments à une distance de l’intervalle h dans une sous-liste.

Étape 3) Triez ces sous-listes en utilisant le tri par insertion.

Étape 4) Définissez un nouvel intervalle, h=h/2.

Étape 5) Si h>0, passez à l’étape 2. Sinon, passez à l’étape 6.

Étape 6) La sortie résultante sera le tableau trié.

Comment fonctionne le tri Shell

Dans le tri par insertion, les éléments sont déplacés d’une seule position à la fois. Au contraire, le tri shell divise le tableau en morceaux plus petits en fonction de la valeur de l'intervalle et exécute un tri par insertion sur ces morceaux.

Progressivement, la valeur de l'intervalle diminue et la taille des morceaux divisés augmente. Comme les pièces sont triées individuellement au préalable, la fusion de ces pièces nécessite moins d'étapes que le tri par insertion.

Le following GIF montre une démonstration du tri par shell. Dans cette démo, les valeurs indiquées en rouge et en bleu sont comparées et échangées en fonction du tri par insertion. Ensuite, l'intervalle diminue et le tri shell lance le tri par insertion dans ces données presque triées.

Travaux de tri des coquilles

Fonctionnement de l'algorithme de tri Shell

Voyons un peu plus loinwing exemple d'un algorithme de tri shell. Dans cet exemple, nous trierons les éléments suivantswing tableau utilisant le tri shell :

Fonctionnement de l'algorithme de tri Shell

Étape 1) Ici, la taille du tableau est de 8. Ainsi, la valeur de l'intervalle sera h = 8/2 ou 4.

Étape 2) Maintenant, nous allons stocker tous les éléments à une distance de 4. Pour notre cas, les sous-listes sont - {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Fonctionnement de l'algorithme de tri Shell

Étape 3) Désormais, ces sous-listes seront triées à l'aide du tri par insertion, où une variable temporaire est utilisée pour comparer les deux nombres et trier en conséquence.

Le tableau serait comme suitwing après les opérations d'échange-

Fonctionnement de l'algorithme de tri Shell

Étape 4) Maintenant, nous allons diminuer la valeur initiale de l'intervalle. Le nouvel intervalle sera h=h/2 ou 4/2 ou 2.

Étape 5) Comme 2>0, nous passerons à l'étape 2 pour stocker tous les éléments à une distance de 2. Pour cette fois, les sous-listes sont-

{1, 5, 8, 7}, {4, 2, 6, 3}

Fonctionnement de l'algorithme de tri Shell

Ensuite, ces sous-listes seront triées par tri par insertion. Après avoir comparé et échangé la première sous-liste, le tableau serait le suivantwing.

Fonctionnement de l'algorithme de tri Shell

Après avoir trié la deuxième sous-liste, le tableau d'origine sera :

Fonctionnement de l'algorithme de tri Shell

Là encore, l’intervalle sera diminué. Maintenant, l'intervalle sera h=h/2 ou 2/1 ou 1. Nous utiliserons donc l'algorithme de tri par insertion pour trier le tableau modifié.

Following est la représentation procédurale étape par étape du tri par insertion.

Fonctionnement de l'algorithme de tri Shell

Fonctionnement de l'algorithme de tri Shell

Fonctionnement de l'algorithme de tri Shell

L'intervalle est à nouveau divisé par 2. A ce moment, l'intervalle devient 0. On passe donc à l'étape 6.

Étape 6) Comme l'intervalle est 0, le tableau est trié selon cette heure. Le tableau trié est-

Fonctionnement de l'algorithme de tri Shell

Pseudo-code

Start
Input array an of size n
for (interval = n / 2; interval & gt; 0; interval /= 2)
    for (i = interval; i & lt; n; i += 1)
        temp = a[i];
for (j = i; j & gt; = interval & amp; & amp; a[j - interval] & gt; temp; j -= interval)
    a[j] = a[j - interval];
a[j] = temp;
End

Programme de tri Shell en C/C++

Contribution:

//Shell Sort Program in C/C++
#include <bits/stdc++.h>
using namespace std;
void ShellSort(int data[], int size) {
    for (int interval = size / 2; interval > 0; interval /= 2) {
        for (int i = interval; i < size; i += 1) {
            int temp = data[i];
            int j;
            for (j = i; j >= interval && data[j - interval] > temp; j -= interval) {
                data[j] = data[j - interval];
            }
            data[j] = temp;
        }
    }
}
int main() {
    int data[] = {8, 6, 7, 2, 1, 4, 5, 3};
    int size = sizeof(data) / sizeof(data[0]);
    ShellSort(data, size);
    cout << "Sorted Output: \n";
    for (int i = 0; i < size; i++)
        cout << data[i] << " ";
    cout << "\n";
}

Sortie :

Sorted Output:

1 2 3 4 5 6 7 8

Exemple de tri de shell en Python

Contribution:

#Shell Sort Example in Python
def ShellSort(data, size):
    interval = size // 2
    while interval > 0:
        for i in range(interval, size):
            temp = data[i]
            j = i
            while j >= interval and data[j - interval] > temp:
                data[j] = data[j - interval]
                j -= interval
            data[j] = temp
        interval //= 2
data = [8, 6, 7, 2, 1, 4, 5, 3]
ShellSort(data, len(data))
print('Sorted Output:')
print(data)

Sortie :

Sorted Output:
[1, 2, 3, 4, 5, 6, 7, 8]

Applications du tri des coques

Voici les applications importantes de Shell Sort :

  • Le tri Shell est utilisé dans le noyau Linux car il n'utilise pas de pile d'appels.
  • La bibliothèque uClbc utilise le tri Shell.
  • Le compresseur bzip2 utilise le tri Shell pour arrêter de dépasser la récursion.

Avantages et inconvénients du tri des coquilles

Avantages Inconvénients
Aucun appel de pile n'est requis. Pas efficace pour les tableaux de grande taille.
Mise en œuvre facile. Inefficace pour les éléments largement répandus.
Efficace pour les éléments moins espacés.

Shell Tri ComplexAnalyse de la ville

Temps Complexité du tri des coques

L'heure arriveplexLa qualité de l'algorithme de tri du shell est O (n ^ 2). Le raisonnement est le suivant :

Pour le meilleur des cas, le nombre total de tests pour tous les intervalles lorsque le tableau était précédemment disposé est égal à log n. Ainsi le complexity serait O(n*log n).

Dans le pire des cas, considérons que le tableau est constitué de telle manière que les éléments nécessitent le plus grand nombre de comparaisons. Ensuite, tous les éléments ne seront comparés et commutés qu’à la dernière itération. Par conséquent, le total des comparaisons requises pour l’incrément final est O(n^2).

En conclusion, le moment est venuplexles villes seraient

  1. Meilleur cas complexité : O(n*log n)
  2. Cas moyen complexité : O(n*log n)
  3. Dans le pire des casplexité : O(n^2)

Le temps de fonctionnement complexLa qualité du tri des coques dépend fortement des séquences d'incréments d'espacement utilisées. Cependant, la meilleure séquence d’incréments pour le tri shell est encore inconnue.

Shell Sort Space Complexity

Dans ce tri comparatif, nous n’avons besoin d’aucun espace auxiliaire supplémentaire. Ainsi l'espace complexLa qualité de ce type d’algorithme est O(1).