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

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

## C++ Sorting: Exercise-13 with Solution

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

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

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, " "));

// 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: