Algorithme de tri Radix dans la structure de données

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

Le tri par base est un algorithme de tri non comparatif. Il fonctionne en regroupant les éléments.ping Les chiffres individuels des éléments à trier sont extraits. Une technique de tri stable est ensuite utilisée pour organiser les éléments selon leur base. Il s'agit d'un algorithme de tri linéaire.

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

• On détermine l'élément maximal et on calcule le nombre de chiffres de cet élément. Cela donne le nombre d'itérations effectuées par le processus de tri.
• Grouping les chiffres individuels des éléments à la même position significative dans chaque itération.
• Le groupeping Le processus commence par le chiffre le moins significatif et se termine par le chiffre le plus significatif.
• Tri des éléments en fonction des chiffres à cette position significative.
• Le tri par base conserve l'ordre relatif des éléments ayant la même valeur de clé. Cette propriété lui confère sa stabilité.

La dernière itération renvoie une liste complètement triée.

Fonctionnement de l'algorithme de tri Radix

Liste des entiers à trier

Trions la liste d'entiers de la figure ci-dessus par ordre croissant en utilisant le tri par base.

Voici les étapes à suivre pour effectuer le processus de tri par base :

Étape 1) Identifiez l'élément maximal de la liste. Ici, il s'agit de 835.

Étape 2) Comptez ses chiffres. 835 a 3 chiffres, donc le nombre d'itérations est de 3.

Étape 3) Déterminez la base. Comme il s'agit d'un nombre décimal, la base est 10.

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

a) Première itération

Tri par le dernier chiffre

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

Étape 1) Pour obtenir le chiffre des unités d'un entier, calculez le modulo 10. Par exemple, 623 modulo 10 donne 3 et 248 modulo 10 donne 8.

Étape 2) Utilisez le tri par dénombrement ou un autre tri stable pour organiser les entiers selon leur chiffre le moins significatif. Sur la figure, 248 se trouve dans le 8e compartiment, 623 dans le 3e, et ainsi de suite.

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

Liste après la première itération

La liste n'est pas encore triée et nécessite d'autres itérations.

b) Deuxième itération

Tri basé sur les chiffres à la place des dizaines

Dans cette itération, nous prenons en compte le chiffre des dizaines pour le processus de tri.

Étape 1) Divisez les entiers par 10. Par exemple, 248 divisé par 10 donne 24.

Étape 2) Modifiez le résultat de l'étape 1 par 10. 24 mod 10 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 maintenant à ceci :

Liste après la deuxième itération

La liste n'est pas encore complètement triée car elle n'est pas encore en ordre croissant.

c) Troisième itération

Tri basé sur les chiffres des centaines

Pour la dernière itération, nous voulons obtenir le chiffre le plus significatif. Dans ce cas, il s'agit du chiffre des centaines pour chacun des entiers de la liste.

Étape 1) Divisez les entiers par 100. Par exemple, 415 divisé par 100 donne 4.

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

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

Liste après la troisième itération

La liste est désormais triée par ordre croissant. La dernière itération est terminée et le processus de tri est achevé.

Pseudocode de l'algorithme de tri Radix

Voici le pseudocode de l'algorithme de tri par base :

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 jth 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 in the jth place
    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 integer
    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 in 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

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

Sortie :

[162, 248, 415, 623, 835]

Analyse de la complexité du tri par base

Il existe deux types de complexité à prendre en compte : 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 caractéristiques à prendre en compte pour la complexité spatiale :

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

Il arrive que cette base soit 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 le tri par base inefficace en termes d'espace :

• É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

En utilisant le tri par dénombrement comme sous-routine, chaque itération prend O(n + b) temps. Si d itérations existent, la durée totale d’exécution devient O(d * (n + b))Ici, « O » désigne 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 significativement plus grand que n.

Comparaison du tri par base avec d'autres méthodes de tri Algorithms

La complexité du tri par base dépend de la taille du nombre. Dans le meilleur des cas comme dans le cas moyen, elle est de O(d * (n + b)). Les performances varient selon l'algorithme de tri interne : le tri par dénombrement est la norme, mais tout tri stable convient.

Applications de l'algorithme de tri Radix

Les principales applications du tri par base sont :

• Le tri par base peut être utilisé comme algorithme de localisation lorsque de grandes plages de valeurs sont impliquées.
• Il est utilisé pour construire un tableau de suffixes dans l'algorithme DC3.
• Il est utilisé dans les machines séquentielles à accès aléatoire où les enregistrements sont indexés par des identifiants de largeur fixe.

FAQ