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 Shell surmonte la complexité moyenne du temps de 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 GIF suivant montre une démonstration du tri 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.

Fonctionnement de l'algorithme de tri Shell

Voyons un exemple suivant d'algorithme de tri shell. Dans cet exemple, nous allons trier le tableau suivant à l'aide du 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}.

É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 ressemblerait à ce qui suit après les opérations d'échange :

É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}

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 suivant.

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

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é.

Voici la description procédurale étape par étape du tri par insertion.

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-

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++

Entrées :

//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 dans Python

Entrées :

#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	Désavantages
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.

Analyse de la complexité du tri des coques

Complexité temporelle du tri des coques

La complexité temporelle de l'algorithme de tri 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, la complexité 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, les complexités temporelles seraient

1. Complexité du meilleur cas : O(n*log n)
2. Complexité moyenne des cas : O(n*log n)
3. Complexité dans le pire des cas : O(n^2)

La complexité du temps d'exécution du tri shell dépend fortement des séquences d'incrémentation d'espacement utilisées. Cependant, la meilleure séquence d’incréments pour le tri shell est encore inconnue.

Complexité spatiale du tri des coques

Dans ce tri comparatif, nous n’avons besoin d’aucun espace auxiliaire supplémentaire. Ainsi, la complexité spatiale de ce type d’algorithme est O(1).