Algorithme de tri Radix dans la structure de données

Qu'est-ce que l'algorithme de tri Radix ?

Radix Sort est un algorithme de tri non comparatif. Il fonctionne en regroupant les chiffres individuels des éléments à trier. Une technique de tri stable est ensuite utilisée pour organiser les éléments en fonction de leur base. Il s'agit d'un algorithme de tri linéaire.

Le processus de tri implique les propriétés suivantes :

Trouver l'élément maximum et acquérir le nombre de chiffres de cet élément. Cela nous donne le nombre d’itérations que suivra le processus de tri.
Regroupez les chiffres individuels des éléments à la même position significative à chaque itération.
Le processus de regroupement commencera par le chiffre le moins significatif et se terminera par le chiffre le plus significatif.
Trier les éléments en fonction des chiffres à cette position significative.
Maintenir l'ordre relatif des éléments qui ont la même valeur clé. Cette propriété du tri par base en fait un tri stable.

L'itération finale nous donnera une liste complètement triée.

Fonctionnement de l'algorithme de tri Radix

Essayons de trier la liste des entiers dans la figure ci-dessus par ordre croissant à l'aide de l'algorithme Radix Sort.

Voici les étapes pour effectuer le processus de tri Radix :

Étape 1) Identifiez l'élément avec la valeur maximale dans la liste. Dans ce cas, il s’agit de 835.

Étape 2) Calculez le nombre de chiffres de l'élément maximum. 835 a exactement 3 chiffres.

Étape 3) Déterminez le nombre d'itérations en fonction de l'étape 2. 835 a 3 chiffres, ce qui signifie que le nombre d'itérations sera de 3.

Étape 4) Déterminez la base des éléments. Puisqu’il s’agit d’un système décimal, la base sera 10.

Étape 5) Commencez la première itération.

a) Première itération

Dans la première itération, nous considérons la valeur unitaire de chaque élément.

Étape 1) Modifiez l'entier par 10 pour obtenir la place unitaire des éléments. Par exemple, 623 mod 10 nous donne la valeur 3, et 248 mod 10 nous donne 8.

Étape 2) Utilisez le tri par comptage ou tout autre tri stable pour organiser les entiers selon leur chiffre le moins significatif. Comme le montre la figure, 248 tomberont sur le 8ème seau. 623 tomberont sur le 3ème seau et ainsi de suite.

Après la première itération, la liste ressemble désormais à ceci.

Comme vous pouvez le voir sur la figure ci-dessus, la liste n'est pas encore triée et nécessite plus d'itérations pour être entièrement triée.

b) Deuxième itération

Dans cette itération, nous considérerons le chiffre à la 10^th lieu pour le processus de tri.

Étape 1) Divisez les entiers par 10. 248 divisé par 10 nous donne 24.

Étape 2) Modifiez la sortie de l'étape 1 par 10. 24 mod 10 nous donne 4.

Étape 3) Suivez l'étape 2 de l'itération précédente.

Après la deuxième itération, la liste ressemble désormais à ceci

Vous pouvez voir sur la figure ci-dessus que la liste n’est toujours pas complètement triée car elle n’est pas encore par ordre croissant.

c) Troisième itération

Pour la dernière itération, nous voulons obtenir le chiffre le plus significatif. Dans ce cas, c'est le 100^thplace pour chacun des entiers de la liste.

Étape 1) Divisez les entiers par 100… 415 divisé par 100 nous donne 4.

Étape 2) Modifiez le résultat de l'étape 1 par 10. 4 mod 10 nous donne à nouveau 4.

Étape 3) Suivez l'étape 3 de l'itération précédente.

Comme nous pouvons le voir, la liste est désormais triée par ordre croissant. La dernière itération est terminée et le processus de tri est maintenant terminé.

Pseudocode de l'algorithme de tri Radix

Voici le pseudo-code de l'algorithme de tri Radix

radixSortAlgo(arr as an array)
  Find the largest element in arr
  maximum=the element in arr that is the largest
  Find the number of digits in maximum
  k=the number of digits in maximum 
  Create buckets of size 0-9 k times
for j -> 0 to k
  Acquire the j^th place of each element in arr. Here j=0 represents the least significant digit.
  Use a stable sorting algorithm like counting sort to sort the elements in arr according to the digits of the elements in the j^thplace
   arr = sorted elements

C++ Programme pour implémenter le tri Radix

#include <iostream>
using namespace std;
// Function to get the largest element in an array
int getMaximum(int arr[], int n) {
  int maximum = arr[0];
  for (int i = 1; i < n; i++) {
    if (maximum < arr[i]) maximum = arr[i];
  }
  return maximum;
}
// We are using counting sort to sort the elements digit by digit
void countingSortAlgo(int arr[], int size, int position) {
  const int limit = 10;
  int result[size];
  int count[limit] = {0};
  // Calculating the count of each integers
  for (int j = 0; j < size; j++) count[(arr[j] / position) % 10]++;
  // Calculating the cumulative count
  for (int j = 1; j < limit; j++) {
    count[j] += count[j - 1];
  }
  // Sort the integers
  for (int j = size - 1; j >= 0; j--) {
    result[count[(arr[j] / position) % 10] - 1] = arr[j];
    count[(arr[j] / position) % 10]--;
  }
  for (int i = 0; i < size; i++) arr[i] = result[i];
}
// The radixSort algorithm
void radixSortAlgo(int arr[], int size) {
  // Get the largest element in the array
  int maximum = getMaximum(arr, size);
  for (int position = 1; maximum / position > 0; position *= 10)
    countingSortAlgo(arr, size, position);
}
// Printing final result
void printResult(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}
int main() {
  int arr[] = {162, 623, 835, 415, 248};
  int size = sizeof(arr) / sizeof(arr[0]);
  radixSortAlgo(arr, size);
  printResult(arr, size);
}

Sortie :

162 248 415 623 835

Python Programme pour l'algorithme de tri Radix

#Radix Sort using python
def countingSortAlgo(arr, position):
    n = len(arr)
    result = [0] * n
    count = [0] * 10  # Calculating the count of elements in the array arr
    for j in range(0, n):
        element = arr[j] // position
        count[element % 10] += 1  # Calculating the cumulative count
    for j in range(1, 10):
        count[j] += count[j - 1]  # Sorting the elements
    i = n - 1
    while i >= 0:
        element = arr[i] // position
        result[count[element % 10] - 1] = arr[i]
        count[element % 10] -= 1
        i -= 1
    for j in range(0, n):
        arr[j] = result[j]


def radixSortAlgo(arr):  # Acquiring the largest element in the array
    maximum = max(arr)  # Using counting sort to sort digit by digit
    position = 1
    while maximum // position > 0:
        countingSortAlgo(arr, position)
        position *= 10


input = [162, 623, 835, 415, 248]
radixSortAlgo(input)
print(input)

Sortie :

[162,248,415,623,835]

Analyse de la complexité de Radix Sort

Il existe deux types de complexité à considérer, la complexité spatiale et la complexité temporelle.

Complexité spatiale : O(n+b) où n est la taille du tableau et b est la base considérée.
Complexité temporelle : O(d*(n+b)) où d est le nombre de chiffres du plus grand élément du tableau.

Complexité spatiale du tri Radix

Deux fonctionnalités sur lesquelles se concentrer pour la complexité de l'espace

Nombre d'éléments dans le tableau, n.
La base pour représenter les éléments, b.

Parfois, cette base peut être supérieure à la taille du tableau.

La complexité globale est donc O(n+b).

Les propriétés suivantes des éléments de la liste peuvent rendre l'espace de tri par base inefficace :

Éléments avec un grand nombre de chiffres.
La base des éléments est grande, comme les nombres 64 bits.

Complexité temporelle du tri par base

Vous pouvez utiliser le tri par comptage comme sous-programme, car chaque itération prendraeO(n+b) temps. Si d itérations existent, la durée totale d’exécution devient O(d*(n+b)). Ici, « O » signifie la fonction de complexité.

Linéarité du tri par base

Le tri par base est linéaire lorsque

d est constant, où d est le nombre de chiffres du plus grand élément.
b n'est pas beaucoup plus grand par rapport à n.

Comparaisons de Radix Sort avec d'autres algorithmes comparatifs

Comme nous l'avons vu, la complexité du tri Radix est basée sur la taille d'un mot ou d'un nombre. Il aura la même complexité pour les cas moyens et meilleurs. Et c'est O(d*(n+b)). Aussi, cela diffère selon la technique de tri que vous utilisez au milieu. Par exemple, vous pouvez utiliser le tri par comptage ou le tri rapide pour l'algorithme de tri intermédiaire à l'intérieur du tri Radix.

Applications de l'algorithme de tri Radix

Les applications importantes de Radix Sort sont :

Radix Sort peut être utilisé comme algorithme de recherche de localisation où de larges plages de valeurs sont utilisées.
Il est utilisé dans la construction d'un tableau de suffixes dans l'algorithme DC3.
Il est utilisé dans une machine séquentielle à accès aléatoire présente dans un ordinateur typique où les enregistrements sont saisis.