Tri par radix utilisant un tableau dynamique

Introduction

Dans ce laboratoire, nous allons exécuter un algorithme de tri par base en C++ pour trier un tableau en utilisant un tableau dynamique. Le tri par base est un algorithme de tri qui trie en traitant les chiffres individuels dans différentes positions.

Inclure les bibliothèques et configurer la fonction

Commencez par créer un fichier C++ dans le répertoire ~/project nommé main.cpp. Incluez les bibliothèques iostream et vector et configurez une fonction radix_sort qui prend un std::vector d'entiers.

#include <iostream>
#include <vector>
using namespace std;

void radix_sort(vector<int>& nums) {

}

Définir la fonction getMax

Définissez une fonction get_max qui prend un vecteur d'entiers en entrée et renvoie la valeur maximale.

int get_max(vector<int>& nums) {
    int max = nums[0];
    for(int i = 1; i < nums.size(); i++) {
        if(nums[i] > max)
            max = nums[i];
    }
    return max;
}

Définir la fonction CountingSort

Définissez une fonction counting_sort qui prend un vecteur d'entiers, une valeur entière pour la valeur de place actuelle et un vecteur d'entiers pour la sortie. La fonction triera le vecteur en fonction de la valeur de place actuelle en utilisant l'algorithme de tri par comptage.

void counting_sort(vector<int>& nums, int place, vector<int>& output) {
    const int max = 10;
    int count[max];

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

    for(int i = 0; i < nums.size(); i++)
        count[(nums[i] / place) % 10]++;

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

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

    for(int i = 0; i < nums.size(); i++)
        nums[i] = output[i];
}

Définir la fonction RadixSort

Définissez une fonction radix_sort qui prend un vecteur d'entiers en entrée. Cette fonction obtiendra la valeur maximale du vecteur d'entrée et utilisera la fonction counting_sort pour trier le vecteur en fonction de chaque valeur de place.

void radix_sort(vector<int>& nums) {
    int max = get_max(nums);

    for(int place = 1; max / place > 0; place *= 10) {
        vector<int> output(nums.size());
        counting_sort(nums, place, output);
    }
}

Testage

Testez la fonction radix_sort en créant une fonction main qui crée et imprime un vecteur de test.

int main() {
    vector<int> test = {121, 432, 564, 23, 1, 45, 788};
    radix_sort(test);

    for(int num : test)
        cout << num << " ";
    cout << endl;

    return 0;
}

Compiler et exécuter

Compilez et exécutez le programme dans le terminal en utilisant la commande suivante :

g++ main.cpp -o main &&./main

Vous devriez voir la sortie suivante :

1 23 45 121 432 564 788

Résumé

Dans ce laboratoire, nous avons appris à effectuer un algorithme de tri par radix en C++ à l'aide de tableaux dynamiques. L'algorithme de tri par radix fonctionne en traitant les chiffres individuels dans différentes positions et est un algorithme de tri couramment utilisé pour les entiers et les chaînes de caractères.