Ordenamiento por Radix con Array Dinámico

Introducción

En este laboratorio, implementaremos un algoritmo de clasificación radix en C++ para ordenar una matriz utilizando una matriz dinámica. El Radix Sort es un algoritmo de clasificación que ordena procesando dígitos individuales en diferentes posiciones.

Incluir Librerías y Configurar Función

Comience creando un archivo C++ en el directorio ~/proyecto llamado main.cpp. Incluya las bibliotecas iostream y vector y configure una función radix_sort que tome un std::vector de enteros.

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

void radix_sort(vector<int>& nums) {

}

Definir la función getMax

Defina una función get_max que tome un vector de enteros como entrada y devuelva el valor máximo.

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

Definir la función CountingSort

Defina una función counting_sort que tome un vector de enteros, un valor entero para el valor de posición actual y un vector de enteros para la salida. La función ordenará el vector basado en el valor de posición actual utilizando el algoritmo de clasificación por conteo.

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

Definir la función RadixSort

Defina una función radix_sort que tome un vector de enteros como entrada. Esta función obtendrá el valor máximo del vector de entrada y usará la función counting_sort para ordenar el vector basado en cada valor de posición.

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

Pruebas

Pruebe la función radix_sort creando una función main que cree e imprima un vector de prueba.

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

Compilar y ejecutar

Compile y ejecute el programa en la terminal usando el siguiente comando:

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

Debería ver la siguiente salida:

1 23 45 121 432 564 788

Resumen

En este laboratorio, aprendimos cómo realizar un algoritmo de clasificación por radix en C++ utilizando arrays dinámicos. El algoritmo de clasificación por radix funciona procesando dígitos individuales en diferentes posiciones y es un algoritmo de clasificación comúnmente utilizado para enteros y cadenas.