C++ Coding Test Course, Radix Sort

1. Overview of Radix Sort

Radix Sort is a special type of sorting algorithm that is effective when the data to be sorted consists of integers or strings within a specific range. Unlike typical sorting algorithms, Radix Sort sorts based on “digits.” Through this, Radix Sort has a time complexity of O(d(n + k)), where d is the number of digits, n is the number of data to be sorted, and k is the range of values.

2. Principle of Radix Sort

Radix Sort is performed through the following process:

1. Starting from the least significant digit, numbers are sorted based on each digit.
2. Sorting is repeated for each digit.
3. Once sorting is completed for all digits, a fully sorted array is obtained.

Radix Sort is typically implemented as a stable sorting algorithm, meaning that the order of elements with the same value retains their relative positions.

3. Implementation of Radix Sort

Let’s implement Radix Sort in C++. Here is the basic implementation of Radix Sort:

#include <iostream>
#include <vector>

using namespace std;

// Function for sorting based on a specific digit
void countingSort(vector<int> &arr, int exp) {
    int n = arr.size();
    vector<int> output(n);
    int count[10] = {0}; // Range of numbers is 0~9

    // Count occurrences of each digit
    for (int i = 0; i < n; i++) {
        count[(arr[i] / exp) % 10]++;
    }

    // Calculate cumulative sum
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // Build the output array
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // Store the result in the original array
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// Radix Sort function
void radixSort(vector<int> &arr) {
    // Find the maximum value
    int maxVal = *max_element(arr.begin(), arr.end());

    // Sort by each digit
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        countingSort(arr, exp);
    }
}

// Main function
int main() {
    vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
    radixSort(arr);
    
    cout << "Sorted array: ";
    for (int i : arr) {
        cout << i << " ";
    }
    
    return 0;
}
        

This code demonstrates the basic flow of Radix Sort. The countingSort function counts the occurrences for each digit and sorts the elements based on that. The radixSort function calls countingSort for each digit and returns the final sorted array.

4. Example Problem Solved with Radix Sort

Now, let’s present an algorithm problem that can be solved using Radix Sort.

Problem: Sort the given list of integers using Radix Sort.

Input: [170, 45, 75, 90, 802, 24, 2, 66]

Output: [2, 24, 45, 66, 75, 90, 170, 802]

Problem-solving process

1. Find the maximum value, which is confirmed to be 802. This value determines the highest digit.
2. Start with the least significant digit and call countingSort for each digit in the order of 1’s place, 10’s place, and 100’s place.
3. After sorting each digit, the final array will be sorted.

Try solving the problem using Radix Sort!