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.

Practice

1. What is the main idea behind the Radix Sort algorithm?

easy

A. Sort numbers digit by digit starting from the least significant digit

B. Compare each element with every other element and swap if needed

C. Divide the array into halves and sort each half recursively

D. Use a pivot element to partition the array and sort partitions

Solution

1. Step 1: Understand Radix Sort approach

   Radix Sort sorts numbers by processing individual digits starting from the least significant digit (rightmost) to the most significant digit (leftmost).

2. Step 2: Compare with other sorting methods

   Other options describe Bubble Sort, Merge Sort, and Quick Sort, which are different algorithms.

3. Final Answer:

   Sort numbers digit by digit starting from the least significant digit -> Option A

4. Quick Check:

   Radix Sort = Digit by digit sorting [OK]

Hint: Radix Sort processes digits from right to left [OK]

Common Mistakes:

• Confusing Radix Sort with comparison-based sorts
• Thinking it sorts from most significant digit first
• Assuming it uses swapping of elements

2. Which of the following is the correct way to extract the digit at position pos (starting from 0 for least significant digit) from an integer num in C++?

easy

A. (num / (10 * pos)) % 10

B. ((num / (int)pow(10, pos)) % 10)

C. (num % (10 * pos)) / 10

D. (num % pow(10, pos)) / 10

Solution

1. Step 1: Understand digit extraction formula

   To get the digit at position pos, divide num by 10^pos and then take modulo 10.

2. Step 2: Check each option

   ((num / (int)pow(10, pos)) % 10 correctly uses pow(10, pos) for exponentiation and modulo 10 to get the digit.

3. Final Answer:

   ((num / (int)pow(10, pos)) % 10) -> Option B

4. Quick Check:

   Digit extraction = (num / 10^pos) % 10 [OK]

Hint: Divide by 10^pos then mod 10 to get digit [OK]

Common Mistakes:

• Using multiplication instead of exponentiation
• Incorrect order of operations
• Using modulo before division

3. What will be the output of the following C++ code snippet using Radix Sort on array arr = {170, 45, 75, 90, 802, 24, 2, 66}?

void countingSort(int arr[], int n, int exp) {
    int output[n];
    int count[10] = {0};
    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

void radixSort(int arr[], int n) {
    int maxVal = *max_element(arr, arr + n);
    for (int exp = 1; maxVal / exp > 0; exp *= 10)
        countingSort(arr, n, exp);
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);
    radixSort(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

medium

A. 24 2 45 66 75 90 170 802

B. 802 170 90 75 66 45 24 2

C. 2 24 45 66 75 90 170 802

D. 2 24 45 75 66 90 170 802

Solution

1. Step 1: Understand Radix Sort steps on given array

   Radix Sort sorts by digits: first units, then tens, then hundreds. After full sorting, array becomes sorted ascending.

2. Step 2: Trace final sorted array

   Sorted array is: 2 24 45 66 75 90 170 802.

3. Final Answer:

   2 24 45 66 75 90 170 802 -> Option C

4. Quick Check:

   Radix Sort final output = sorted array ascending [OK]

Hint: Radix Sort outputs fully sorted array ascending [OK]

Common Mistakes:

• Confusing intermediate steps with final output
• Misordering numbers with same digits
• Ignoring stable sorting in countingSort

4. Identify the bug in the following Radix Sort counting sort implementation and select the correct fix:

void countingSort(int arr[], int n, int exp) {
    int output[n];
    int count[10] = {0};
    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];
    for (int i = 0; i < n; i++) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

medium

A. Change the last for loop to iterate from n-1 down to 0 for stable sorting

B. Initialize count array with -1 instead of 0

C. Remove the cumulative sum loop for count array

D. Replace output array with a vector for dynamic sizing

Solution

1. Step 1: Identify stable sorting requirement in counting sort

   Counting sort must process elements from right to left to maintain stability.

2. Step 2: Check the for loop direction

   Current loop goes from 0 to n-1, which breaks stability. Changing it to n-1 down to 0 fixes this.

3. Final Answer:

   Change the last for loop to iterate from n-1 down to 0 for stable sorting -> Option A

4. Quick Check:

   Stable counting sort = reverse iteration [OK]

Hint: Counting sort must iterate backward for stability [OK]

Common Mistakes:

• Iterating forward breaks stable sorting
• Misunderstanding count array initialization
• Ignoring cumulative sum step

5. Given an array of strings representing numbers with leading zeros, e.g., {"002", "010", "001", "100"}, how can you adapt Radix Sort to correctly sort them as numbers?

hard

A. Use counting sort only on the first character of each string

B. Sort strings lexicographically using Radix Sort on characters

C. Ignore leading zeros and sort strings as-is with Radix Sort

D. Convert strings to integers first, then apply Radix Sort on integers

Solution

1. Step 1: Understand sorting numeric strings with leading zeros

   Sorting strings lexicographically will not sort numbers correctly if leading zeros exist.

2. Step 2: Convert strings to integers for numeric sorting

   Convert strings to integers to remove leading zeros, then apply Radix Sort on integers for correct numeric order.

3. Final Answer:

   Convert strings to integers first, then apply Radix Sort on integers -> Option D

4. Quick Check:

   Numeric string sorting = convert to int then Radix Sort [OK]

Hint: Convert strings to int before Radix Sort for numeric order [OK]

Common Mistakes:

• Sorting strings lexicographically causes wrong order
• Ignoring leading zeros impact
• Using only first character for sorting