Radix Sort Algorithm in DSA C++ - Build from Scratch

Radix Sort Algorithm

📖 Scenario: You work in a warehouse where packages have unique ID numbers. You need to sort these package IDs quickly to organize shipments.

🎯 Goal: Build a program that sorts a list of package ID numbers using the Radix Sort algorithm.

📋 What You'll Learn

Create a vector called package_ids with the exact values: 170, 45, 75, 90, 802, 24, 2, 66

Create an integer variable called max_num to store the maximum number in package_ids

Implement the Radix Sort logic using a helper function countingSortByDigit that sorts based on digit place

Print the sorted package_ids vector in the format: 2 24 45 66 75 90 170 802

💡 Why This Matters

🌍 Real World

Sorting package IDs quickly helps warehouses organize shipments efficiently and avoid delays.

💼 Career

Understanding Radix Sort is useful for software engineers working on performance-critical sorting tasks and large datasets.

1

Create the initial list of package IDs

Create a std::vector<int> called package_ids with these exact values: 170, 45, 75, 90, 802, 24, 2, 66

DSA C++

#include 
#include 

int main() {
    // Create package_ids vector with given values
    // Your code here
}

Hint

Use std::vector<int> and initialize it with the exact numbers inside curly braces.

2

Find the maximum number in the list

Create an integer variable called max_num and set it to the maximum value in package_ids using a simple loop

DSA C++

#include 
#include 

int main() {
    std::vector package_ids = {170, 45, 75, 90, 802, 24, 2, 66};
    // Find max_num in package_ids
    // Your code here
}

Hint

Start with the first element as max, then check each element to update max_num if bigger.

3

Implement Radix Sort core logic

Write a function called countingSortByDigit that sorts package_ids based on the digit at exp place. Then, in main, use a while loop to call countingSortByDigit for each digit place starting from 1, multiplying exp by 10 each time until max_num / exp is 0

DSA C++

#include 
#include 

// Define countingSortByDigit function here

int main() {
    std::vector package_ids = {170, 45, 75, 90, 802, 24, 2, 66};
    int max_num = package_ids[0];
    for (int i = 1; i  max_num) {
            max_num = package_ids[i];
        }
    }
    // Implement radix sort using countingSortByDigit
    // Your code here
}

Hint

Use counting sort for each digit place starting from 1, then multiply exp by 10 each loop until max_num / exp is 0.

4

Print the sorted package IDs

Print the sorted package_ids vector in one line separated by spaces using a for loop

DSA C++

#include 
#include 

void countingSortByDigit(std::vector& arr, int exp) {
    int n = arr.size();
    std::vector output(n);
    int count[10] = {0};

    for (int i = 0; i = 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    for (int i = 0; i  package_ids = {170, 45, 75, 90, 802, 24, 2, 66};
    int max_num = package_ids[0];
    for (int i = 1; i  max_num) {
            max_num = package_ids[i];
        }
    }

    int exp = 1;
    while (max_num / exp > 0) {
        countingSortByDigit(package_ids, exp);
        exp *= 10;
    }

    // Print sorted package_ids separated by spaces
    // Your code here
}

Hint

Use a for loop to print each number in package_ids separated by spaces, then print a newline.