Algorithme de tri Shell avec exemple

Qu'est-ce que le tri Shell ?

Le tri Shell, également appelé méthode de Shell, est un algorithme de tri efficace basé sur la comparaison en place. Nommé d'après Donald Shell, qui a introduit cette idée en 1959, il s'agit d'une généralisation du tri par insertion qui pallie son comportement quadratique sur des données dispersées.

L'idée fondamentale est de regrouper les éléments éloignés les uns des autres, de trier chaque groupe par insertion, et de réduire progressivement l'écart jusqu'à ce qu'il atteigne un. Le tableau est alors presque trié.

Cet intervalle, ce laps de temps, suit une séquence choisie, comme celle de Shell, de Knuth, d'Hibbard ou de Sedgewick. La version originale de Shell est : n/2, n/4, ..., 1.

Algorithme de tri des coques

Étape 1) Initialisez la valeur d'intervalle h = n/2, où n est la taille du tableau.

Étape 2) Placez tous les éléments situés à une distance de l'intervalle h dans une sous-liste.

Étape 3) Triez chaque sous-liste en utilisant le tri par insertion.

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

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

Étape 6) Le tableau résultant est désormais entièrement trié.

Comment fonctionne le tri Shell

Dans le tri par insertion, les éléments se déplacent d'une position à la fois. Le tri Shell, quant à lui, divise le tableau en sous-listes largement espacées en fonction de l'intervalle et effectue un tri par insertion sur chaque sous-liste.

À mesure que l'intervalle diminue, la taille de la sous-liste augmente. Comme les passages précédents laissent les données partiellement triées, les intervalles plus petits nécessitent beaucoup moins d'échanges que les passages en cours. tri par insertion À partir de zéro. La figure ci-dessous illustre une passe de tri Shell.

Fonctionnement de l'algorithme de tri Shell avec exemple

Trions le tableau ci-dessous à l'aide de Shell Sort.

Étape 1) La taille du tableau est de 8, donc la valeur de l'intervalle initial est h = 8/2 = 4.

Étape 2) Regroupez les éléments à quatre positions d'écart. Sous-listes : {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Étape 3) Triez chaque sous-liste par insertion. Une variable temporaire stocke la valeur insérée pendant le déplacement des éléments. Après les échanges, le tableau ressemble à ceci.

Étape 4) Diminuez l'intervalle. Le nouvel intervalle est h = 4/2 = 2.

Étape 5) Parce que 2 > 0, retournez à l'étape 2 et regroupez les éléments à deux positions d'écart : {1, 5, 8, 7} et {4, 2, 6, 3}.

Triez la première sous-liste. Le tableau devient :

Après avoir trié la deuxième sous-liste :

Diminuez à nouveau l'intervalle à h = 2/2 = 1. Avec un écart d'un, Shell Sort effectue un dernier passage de tri par insertion sur l'ensemble du tableau, comme indiqué ci-dessous.

Étape 6) En divisant à nouveau l'intervalle, on obtient 0. Le tableau est maintenant entièrement trié :

Pseudo-Code pour le tri des coquillages

Start
Input array a of size n
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

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

Le tri Shell est encore présent dans les systèmes modernes où l'espace de pile ou la simplicité sont importants.

• Le noyau Linux Utilise Shell Sort dans les cas où il est important d'éviter une pile d'appels.
• La bibliothèque C embarquée uClibc utilise Shell Sort pour limiter l'utilisation de la mémoire.
• bzip2 utilise Shell Sort pour éviter une récursion profonde lors du tri des blocs.
• Le firmware embarqué privilégie le tri Shell pour les petits ensembles de données où la récursivité est limitée.

Avantages et inconvénients du tri par coquille

Analyse de la complexité du tri des coques

Complexité temporelle du tri des coques

La complexité temporelle du tri Shell dépend de la séquence d'intervalles utilisée.

Dans le meilleur des cas, lorsque le tableau est déjà presque organisé, chaque passage ne nécessite qu'un nombre logarithmique de tests, ce qui donne O(n log n).

Dans le pire des cas, le tableau est agencé de telle sorte que les éléments nécessitent le maximum de comparaisons, et l'incrément final domine à O(n^2) avec la séquence originale de Shell.

1. Complexité du meilleur cas : O(n log n)
2. Complexité moyenne : O(n log n) à O(n^(4/3)) selon la séquence d'intervalles
3. Complexité dans le pire des cas : O(n^2) avec la séquence originale de Shell

La meilleure séquence d'intervalles à usage général reste une question de recherche ouverte, bien que les séquences de Sedgewick et de Ciura donnent de bons résultats en pratique.

Complexité spatiale du tri des coques

Le tri Shell ne nécessite pas de tableaux auxiliaires, donc la complexité spatiale est O(1) quelle que soit la taille de l'entrée, ce qui est l'un de ses plus grands avantages pratiques.

FAQ