Tri à peigne

1. Algorithme de tri à peigne
2. Exemple de tri par peigne
3. Implémentation de l’algorithme de tri en peigne
4. Complexité de l’algorithme de tri à peigne

Le tri à peigne est un algorithme de tri simple basé sur la comparaison. C’est une forme améliorée de tri à bulles. Dans le tri à bulles, les éléments adjacents sont comparés dans chaque passe/phase et éliminent les inversions une par une. En revanche, le tri en peigne commence par utiliser un grand écart et le réduit à chaque fois d’un facteur de réduction de 1.3. Le tri en peigne peut supprimer plusieurs inversions avec un seul échange. Il est basé sur l’idée de tuer les tortues. Les tortues sont les petits éléments vers la fin de la liste, ce qui réduit l’efficacité du tri par bulles et le fait de les tuer améliore considérablement les performances du tri.

Algorithme de tri à peigne

Supposons que nous ayons un tableau non trié A[] contenant n éléments. Nous prendrons le facteur de rétrécissement comme 1.3 car il a été empiriquement prouvé qu’il donne les meilleurs résultats.

Exemple de tri par peigne

Supposons que nous ayons le tableau : (3, 5, 2, 8, 1, 7, 6, 4). Nous allons le trier en utilisant l’algorithme de tri en peigne.

Initialisez gap=8 , swapped=true et SHRINK_FACTOR = 1.3.

• La première passe

gap = 8/1,3 = 6 , swapped = false

• Le deuxième passage

écart" = 6/1,3 = 4 , “échangé” = “faux

• Le troisième passage

gap = 4 / 1,3 = 3, swapped = false

• Le quatrième passage

gap = 3 / 1,3 = 2, swapped = false

• Le cinquième passage

gap = 2 / 1,3 = 1, swapped = false

Nous obtenons le tableau final trié comme : (1, 2, 3, 4, 5, 6, 7, 8).

Implémentation de l’algorithme de tri en peigne

#include <iostream>
using namespace std;

int updateGap(int gap) {
  gap = (gap * 10) / 13;
  if (gap < 1)
    return 1;
  else
    return gap;
}

void combSort(int arr[], int n) {
  int gap = n;
  bool swapped = true;
  while (gap > 1 || swapped == true) {
    gap = updateGap(gap);
    swapped = false;
    for (int i = 0; i < (n - gap); i++) {
      int temp;
      if (arr[i] > arr[i + gap]) {
        temp = arr[i];
        arr[i] = arr[i + gap];
        arr[i + gap] = temp;
        swapped = true;
      }
    }
  }
}

int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  combSort(arr, n);
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Complexité de l’algorithme de tri à peigne

Complexité temporelle

• Cas moyen

La complexité temporelle est de l’ordre du [Big Theta] : O(n²/2^p) où p est le nombre d’incréments.

• Pire cas

La complexité temporelle dans le pire des cas est [Big O] : O(n²).

• Meilleur cas

Dans le meilleur des cas, le tableau est déjà trié ou presque trié. Le meilleur cas de complexité temporelle est [Big Omega] : O(nlogn). Il s’agit d’une amélioration significative par rapport au meilleur cas de complexité temporelle du tri à bulles.

Complexité spatiale

La complexité de l’espace pour cet algorithme est O(n) car l’algorithme de tri en peigne ne nécessite pas d’espace supplémentaire autre que des variables temporaires.