Radix Sort com Array Dinâmico em C++: Tutorial e Implementação

Introdução

Neste laboratório, iremos implementar o algoritmo de ordenação Radix Sort em C++ para ordenar um array utilizando um array dinâmico. Radix Sort é um algoritmo de ordenação que ordena processando dígitos individuais em diferentes posições.

Incluir Bibliotecas e Configurar Função

Comece criando um arquivo C++ no diretório ~/project chamado main.cpp. Inclua as bibliotecas iostream e vector e configure uma função radix_sort que recebe um std::vector de inteiros.

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

void radix_sort(vector<int>& nums) {

}

Definir Função getMax

Defina uma função get_max que recebe um vetor de inteiros como entrada e retorna o 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 Função CountingSort

Defina uma função counting_sort que recebe um vetor de inteiros, um valor inteiro para o valor posicional atual e um vetor de inteiros para a saída. A função irá ordenar o vetor com base no valor posicional atual usando o algoritmo de ordenação por contagem (counting sort).

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 Função RadixSort

Defina uma função radix_sort que recebe um vetor de inteiros como entrada. Esta função obterá o valor máximo do vetor de entrada e usará a função counting_sort para ordenar o vetor com base em cada valor posicional.

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

Testando

Teste a função radix_sort criando uma função main que cria e imprime um vetor de teste.

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 e Executar

Compile e execute o programa no terminal usando o seguinte comando:

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

Você deve ver a seguinte saída:

1 23 45 121 432 564 788

Resumo

Neste laboratório, aprendemos como realizar um algoritmo de ordenação radix (radix sort) em C++ usando arrays dinâmicos. O algoritmo de ordenação radix funciona processando dígitos individuais em diferentes posições e é um algoritmo de ordenação comumente usado para inteiros e strings.

Radix Sort Usando Array Dinâmico