Tri de Shell

1. Algorithme de tri de Shell
2. Exemple de tri de Shell
3. Implémentation de l’algorithme de tri Shell
4. Complexité de l’algorithme de tri de Shell

Le tri de Shell est un algorithme de tri très efficace basé sur la comparaison. Il est considéré comme la généralisation de l’algorithme de tri à bulles ou un algorithme de tri par insertion optimisé. Dans l’algorithme de tri par insertion, nous déplaçons les éléments une position en avant. Mais dans le cas du tri shell, nous déplaçons les éléments h positions en avant. Il commence par trier les éléments très éloignés et réduit progressivement l’écart en fonction d’une séquence pour trier l’ensemble du tableau. Voici quelques-unes des séquences utilisées :

Algorithme de tri de Shell

Supposons que nous ayons un tableau non trié A[] contenant n éléments. Nous utiliserons la séquence originale du shell pour trier le tableau.

Exemple de tri de Shell

Supposons que nous ayons le tableau : (9, 8, 3, 7, 5, 6, 4, 1). Nous allons le trier en utilisant l’algorithme de tri du shell et utiliser la séquence originale du shell pour réduire les intervalles d’écart.

• Première itération

n/2 = 4, les éléments situés à l’intervalle 4 sont comparés et échangés.

A[0] > A[4] → échangé, (5,8,3,7,9,6,4,1).

A[1] > A[5] → échangé, (5,6,3,7,9,8,4,1).

A[2] < A[6]

A[3] > A[7]→ a échangé, (5,6,3,1,9,8,4,7).

Le tableau devient : (5,6,3,1,9,8,4,7).

• Deuxième itération

n/4 = 2, les éléments situés à l’intervalle 2 sont comparés et échangés.

A[0]> A[2]→ échangé, (3,6,5,1,9,8,4,7).

A[1]> A[3]→ échangé, (3,1,5,6,9,8,4,7).

A[0] < A[2] < A[4]

A[1] < A[3] < A[5]

A[2]> A[4] et A[4] > A[6] → ont échangé, (3,1,4,6,5,8,9,7).

A[1] < A[3] < A[5] mais A[5] > A[7] → a été échangé, (3,1,4,6,5,7,9,8).

Le tableau devient : (3,1,4,6,5,7,9,8).

• Troisième itération

n/8 = 1, les éléments situés à l’intervalle 1 sont comparés et échangés.

A[0] > A[1] → échangé, (1,3,4,6,5,7,9,8).

A[0] .. A[2] → trié

A[0] .. A[3] → trié

A[0] .. A[3] → trié mais A[3] > A[4] → échangé, (1,3,4,5,6,7,9,8).

A[0] .. A[5] → trié

A[0] .. A[6] → trié

A[0] .. A[6] → trié mais A[6] > A[7] → échangé, (1, 3, 4, 5, 6, 7, 8, 9).

Implémentation de l’algorithme de tri Shell

#include <bits/stdc++.h>
using namespace std;
void shellSort(int arr[], int n) {
  for (int gap = n / 2; gap > 0; gap /= 2) {
    for (int i = gap; i < n; i += 1) {
      int temp = arr[i];
      int j;
      for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
        arr[j] = arr[j - gap];
      arr[j] = temp;
    }
  }
}
int main() {
  int n = 8;
  int arr[8] = {9, 8, 3, 7, 5, 6, 4, 1};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  shellSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Complexité de l’algorithme de tri de Shell

Complexité temporelle

• Cas moyen

La complexité dépend de la séquence choisie pour le tri. La complexité temporelle est de l’ordre du [Big Theta] : O(nlog(n)²).

• Pire cas

La complexité temporelle dans le pire des cas pour le tri de Shell est toujours inférieure à O(n²). Plus précisément, selon le théorème de Poonen, elle est donnée par Θ(nlogn)²/(log log n)²) ou Θ(nlog n)²/log log n) ou Θ(n(log n)²) ou quelque chose entre les deux. La complexité temporelle dans le pire des cas est [Big O] : moins que O(n²).

• Meilleur cas

Le meilleur cas se présente lorsque le tableau est déjà trié et que les comparaisons requises pour chaque intervalle sont identiques à la taille du tableau. Le meilleur cas de complexité temporelle est [Big Omega] : O(nlogn).

Complexité spatiale

La complexité spatiale de l’algorithme de tri de Shell est O(n) car aucune mémoire supplémentaire autre qu’une variable temporaire n’est nécessaire.