C++ Radix sort Exercises: Sort a collection of integers using the Radix sort

Last update on December 20 2024 12:25:24 (UTC/GMT +8 hours)

Write a C++ program to sort a collection of integers using Radix sort.

Sample Solution:

C++ Code :

#include <algorithm>
#include <iostream>
#include <iterator>

// Radix sort comparator for 32-bit two's complement integers
class radix_test {
    const int bit; // bit position [0..31] to examine
public:
    radix_test(int offset) : bit(offset) {} // Constructor

    // Function call operator to compare bits based on position
    bool operator()(int value) const {
        if (bit == 31) // Sign bit: negative int to left partition
            return value < 0;
        else
            return !(value & (1 << bit)); // 0 bit to left partition
    }
};

// Least significant digit radix sort
void lsd_radix_sort(int *first, int *last) {
    for (int lsb = 0; lsb < 32; ++lsb) // Iterating through bits from least significant to most significant
    {
        std::stable_partition(first, last, radix_test(lsb)); // Using std::stable_partition with radix_test as comparator
    }
}

// Most significant digit radix sort (recursive)
void msd_radix_sort(int *first, int *last, int msb = 31) {
    if (first != last && msb >= 0) { // Base case check
        int *mid = std::partition(first, last, radix_test(msb)); // Partition based on the most significant bit
        msb--; // Decrement most significant bit for the next recursive calls
        msd_radix_sort(first, mid, msb); // Recursively sort the left partition
        msd_radix_sort(mid, last, msb); // Recursively sort the right partition
    }
}

// Test radix_sort
int main() {
    int data[] = {125, 0, 695, 3, -256, -5, 214, 44, 55};

    std::cout << "Before Sorting:" << std::endl;
    std::copy(data, data + 8, std::ostream_iterator<int>(std::cout, " "));

    lsd_radix_sort(data, data + 8); // Performing LSD Radix Sort
    // msd_radix_sort(data, data + 8); // Use this line for MSD Radix Sort

    std::cout << "\nAfter Sorting:" << std::endl;
    std::copy(data, data + 8, std::ostream_iterator<int>(std::cout, " "));

    return 0;
}

Sample Output:

Before Sorting:
125 0 695 3 -256 -5 214 44 
After Sorting:
-256 -5 0 3 44 125 214 695

Flowchart:

C++ Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a C++ program to sort a collection of integers using the Quick sort.
Next: Write a C++ program to sort a collection of integers using the Selection sort.