Tri par paquets

1. Algorithme de tri par paquets
2. Exemple de tri par paquet
3. Mise en œuvre de l’algorithme de tri par paquet
4. Complexité de l’algorithme de tri par paquets

Tri par paquets est un algorithme de tri de type comparaison. Il trie les éléments en les répartissant dans des paquets ou des bacs et en utilisant un algorithme différent (généralement le tri par insertion) pour trier le contenu de chaque paquet. Les paquet individuels triés sont ensuite ajoutés ensemble pour obtenir le tableau trié final. Cette approche de l’algorithme de tri est également connue sous le nom d’approche de collecte par dispersion. Elle est principalement utilisée lorsque l’entrée est uniformément distribuée sur une plage comme les flotteurs allant de 0.00 à 1.00.

Algorithme de tri par paquets

Supposons que nous ayons un tableau non trié A[] contenant n éléments.

Exemple de tri par paquet

Supposons que nous ayons le tableau : (0.22,0.33,0.1,0.45,0.38,0.55,0.21,0.31). Nous allons le trier en utilisant l’algorithme de tri par paquet.

• Faites 10 godets de la plage 0.1.

• Après avoir inséré des éléments dans des paquetx, on obtient :

• Trier les paquetx individuels à obtenir :

En additionnant tous les résultats, on obtient le tableau final trié comme suit (0.1,0.21,0.22,0.31,0.33,0.38,0.45,0.55).

Mise en œuvre de l’algorithme de tri par paquet

#include <bits/stdc++.h>
using namespace std;

void bucketSort(float *array, int size) {
  vector<float> bucket[size];
  // insert elements into different buckets.
  for (int i = 0; i < size; i++) {
    bucket[int(size * array[i])].push_back(array[i]);
  }
  // sort individual buckets.
  for (int i = 0; i < size; i++) {
    sort(bucket[i].begin(), bucket[i].end());
  }

  int index = 0;
  for (int i = 0; i < size; i++) {
    while (!bucket[i].empty()) {
      array[index++] = *(bucket[i].begin());
      bucket[i].erase(bucket[i].begin());
    }
  }
}

int main() {
  int n = 8;
  float arr[8] = {0.22, 0.33, 0.1, 0.45, 0.38, 0.55, 0.21, 0.31};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  bucketSort(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 par paquets

Complexité temporelle

• Cas moyen

Le cas moyen se produit si les éléments sont distribués de manière aléatoire, et l’algorithme donne des résultats très efficaces. La complexité temporelle est de l’ordre de [Big Theta] : O(n+k). C’est l’un des rares algorithmes dont la complexité temporelle est linéaire en moyenne, et cette complexité est maintenue si la somme des carrés des tailles des godets est linéaire en n.

• Pire cas

Le pire cas se produit lorsque de nombreux éléments sont à proximité dans le répaquet et sont regroupés dans le même paquet. Cela supprime tous les avantages de la division des entrées en godets, et la complexité totale devient dépendante de l’algorithme de tri utilisé. Le tri par insertion a une complexité temporelle dans le pire des cas de O(n²) lorsque les éléments sont en ordre inversé. Par conséquent, la complexité temporelle dans le pire des cas est [Big O] : O(n²).

• Meilleur cas

Dans le meilleur des cas, les éléments sont uniformément répartis dans tous les paquetx, ou nous obtenons un tableau déjà trié. La complexité temporelle totale comprend le temps nécessaire pour créer les godets O(n) et le temps nécessaire pour trier O(k). Le meilleur cas de complexité temporelle est [Big Omega] : O(n+k).

Complexité spatiale

La complexité spatiale la plus défavorable pour l’algorithme de tri des godets est O(n*k), où n est le nombre d’éléments et k est le nombre de godets. La complexité spatiale peut être réduite à O(n+k) en réduisant l’espace pour contenir tous les éléments et en stockant des pointeurs vers le début du bac.