Tri comptage

Le tri comptage est un algorithme de tri non comparatif. Il trie un tableau en comptant les occurrences de chaque élément unique. Il effectue un hachage partiel du comptage des éléments uniques et effectue ensuite des calculs pour trouver l’indice de chaque élément dans le tableau final trié. C’est un algorithme assez rapide mais qui ne convient pas aux grands ensembles de données. Il est utilisé comme sous-programme dans tri par base.

Algorithme de tri comptage

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

Exemple de tri de comptage

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

• maxm = 7
• minm = 2
• plage = 6
• count et output sont initialisés avec des zéros.

• Tableau de count après avoir calculé le nombre de tous les éléments.

• Tableau de count après cumul de la somme des éléments.

• Première itération : A[7]=2

• Deuxième itération : A[6]=4

• Troisième itération : A[5]=5

• Quatrième itération : A[4]=4

• Cinquième itération : A[3]=7

• Sixième itération : A[2]=2

• Septième itération : A[1]=3

• Huitième itération : A[0]=6

Enfin, nous stockons le tableau de output dans A et nous obtenons le tableau trié - 2, 2, 3, 4, 4, 5, 6, 7.

Implémentation de l’algorithme de tri du comptage

#include <iostream>
using namespace std;
const int N = 10;

int maxm(int arr[], int n) {
  int max = arr[0];
  for (int i = 1; i < n; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

int minm(int arr[], int n) {
  int min = arr[0];
  for (int i = 1; i < n; i++) {
    if (arr[i] < min) {
      min = arr[i];
    }
  }
  return min;
}

void countingSort(int arr[], int n) {
  int min = minm(arr, n);
  int max = maxm(arr, n);
  int range = max - min + 1;
  int count[range] = {};
  int output[n];
  for (int i = 0; i < n; i++) count[arr[i] - min]++;

  for (int i = 1; i < range; i++) count[i] += count[i - 1];

  for (int i = n - 1; i >= 0; i--) {
    output[count[arr[i] - min] - 1] = arr[i];
    count[arr[i] - min]--;
  }

  for (int i = 0; i < n; i++) arr[i] = output[i];
}

int main() {
  int n = 7;
  int arr[7] = {3, 5, 1, 1, 4, 2, 1};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  countingSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Cette mise en œuvre fonctionne également pour les chiffres négatifs.

Complexité de l’algorithme de tri du comptage

Complexité temporelle

• Cas moyen

Le tri comptage itére deux fois tous les éléments n et une fois le tableau count. Il a donc une complexité temporelle de O(n + b) où b est la plage d’entrée. Comme b est souvent petit, la complexité temporelle du tri de comptage est de l’ordre de [Big Theta] : O(n).

• Pire cas

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

• Meilleur cas

Le meilleur exemple de complexité temporelle est [Big Omega] : O(n). C’est la même chose que la complexité temporelle dans le pire des cas.

Complexité spatiale

La complexité spatiale pour l’algorithme de tri par comptage est O(n+b), où b est la plage d’entrée. Elle provient des tableaux count et output. Parfois, b peut être plus grand que n, mais si b est petit, on dit que la complexité temporelle est de O(n).