Radix Sort Using Dynamic Array

Introduction

In this lab, we will perform a radix sort algorithm in C++ to sort an array using a dynamic array. Radix Sort is a sorting algorithm that sorts by processing individual digits in different positions.

Include Libraries and Set Up Function

Start by creating a C++ file in the ~/project directory named main.cpp. Include the iostream and vector libraries and set up a radix_sort function that takes in a std::vector of integers.

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

void radix_sort(vector<int>& nums) {

}

Define getMax Function

Define a get_max function that takes an integer vector as input and returns the maximum value.

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

Define CountingSort Function

Define a counting_sort function that takes an integer vector, an integer value for the current place value, and an integer vector for the output. The function will sort the vector based on the current place value using the counting sort algorithm.

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

Define RadixSort Function

Define a radix_sort function that takes an integer vector as input. This function will get the maximum value from the input vector and use the counting_sort function to sort the vector based on each place value.

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

Testing

Test the radix_sort function by creating a main function that creates and prints a test vector.

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

Compile and Run

Compile and run the program in the terminal using the following command:

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

You should see the following output:

1 23 45 121 432 564 788

Summary

In this lab, we learned how to perform a radix sort algorithm in C++ using dynamic arrays. The radix sort algorithm works by processing individual digits in different positions and is a commonly used sorting algorithm for integers and strings.