Tri par base

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

Le tri par base est un algorithme de tri non comparatif. Cet algorithme évite les comparaisons en insérant des éléments dans des godets selon la base (Radix/Base est le nombre de chiffres uniques utilisés pour représenter les nombres. Par exemple, les nombres décimaux ont dix chiffres uniques). Il trie les éléments en fonction des chiffres des éléments individuels. Il effectue un tri par comptage sur les chiffres du chiffre le moins significatif au chiffre le plus significatif. Il a également été appelé tri par paquets ou tri numérique et est très utile sur les machines parallèles.

Algorithme de tri par base

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

Exemple de tri Radix

Supposons que nous ayons le tableau : (1851, 913, 1214, 312, 111, 23, 41, 9). Nous allons le trier en utilisant l’algorithme de tri radix.

Dans la première itération, nous trions selon l’unité de place, puis nous nous déplaçons vers des dizaines, des centaines et des milliers de places pour obtenir le tableau final trié comme suit : 9, 23, 41, 111, 312, 913, 1214, 1851.

Implémentation de l’algorithme de tri par base

#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;
}

void countingSort(int arr[], int n, int place) {
  int output[n];
  int count[N];

  for (int i = 0; i < N; ++i) count[i] = 0;

  for (int i = 0; i < n; i++) count[(arr[i] / place) % 10]++;

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

  for (int i = n - 1; i >= 0; i--) {
    output[count[(arr[i] / place) % 10] - 1] = arr[i];
    count[(arr[i] / place) % 10]--;
  }

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

void radixsort(int arr[], int n) {
  int max = maxm(arr, n);
  for (int place = 1; max / place > 0; place *= 10) countingSort(arr, n, place);
}

int main() {
  int n = 5;
  int arr[5] = {1851, 913, 1214, 312, 111};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  radixsort(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 base

Complexité temporelle

• Cas moyen

Le tri de base a une complexité temporelle de O(n + b) où b est la plage d’entrée. S’il y a des chiffres d dans l’élément maximum maxm, alors la complexité temporelle du tri Radix devient O(d*(n + b)). Puisque d et b sont généralement petits, la complexité temporelle 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 base est O(n+b), où b est la plage d’entrée. Elle provient des tableaux count et output du tri par base. Parfois, b peut être plus grand que n, ce qui rend la complexité non linéaire.