C++ • SORTING ALGORITHM Radix Sort

C++ • SORTING ALGORITHM

Radix Sort

ALGORITHM

Radix Sort

TIME COMPLEXITY

O(d * (n + b))

SPACE COMPLEXITY

O(n + b)

ORDER

Ascending

C++ Implementation

radix_sort.cpp

#include <iostream>
using namespace std;

class ArraySort
{
    int n;
    int a[100];

    // A utility function to get the maximum value in a[]
    int getMax()
    {
        int mx = a[0];
        for (int i = 1; i < n; i++)
            if (a[i] > mx)
                mx = a[i];
        return mx;
    }

    // A function to do counting sort of a[] according to the digit represented by exp
    void countSort(int exp)
    {
        int output[100]; // output array
        int i, count[10] = {0};

        // Store count of occurrences in count[]
        for (i = 0; i < n; i++)
            count[(a[i] / exp) % 10]++;

        // Change count[i] so that count[i] now contains actual
        // position of this digit in output[]
        for (i = 1; i < 10; i++)
            count[i] += count[i - 1];

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

        // Copy the output array to a[], so that a[] now
        // contains sorted numbers according to current digit
        for (i = 0; i < n; i++)
            a[i] = output[i];
    }

public:

    // Constructor
    ArraySort()
    {
        n = 0;
    }

    // Input function
    void input()
    {
        cout << "Enter length of array: ";
        cin >> n;

        cout << "Enter array elements: ";

        for(int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
    }

    // Radix Sort function
    void radixSort()
    {
        // Find the maximum number to know number of digits
        int m = getMax();

        // Do counting sort for every digit. Note that instead
        // of passing digit number, exp is 10^i where i is
        // the current digit position (1, 10, 100, ...)
        for (int exp = 1; m / exp > 0; exp *= 10)
            countSort(exp);
    }

    // Output function
    void output()
    {
        cout << "Sorted Array: ";

        for(int i = 0; i < n; i++)
        {
            cout << a[i] << " ";
        }
    }
};

int main()
{
    ArraySort obj;

    obj.input();
    obj.radixSort();
    obj.output();

    return 0;
}

Sample Input

Enter length of array: 5
Enter array elements:
170 45 75 90 802

Output

Sorted Array:
45 75 90 170 802

Line-by-Line Explanation

Code

Meaning

#include <iostream>

Includes standard input/output stream functions.

class ArraySort

Creates a class named ArraySort containing the array and sorting methods.

int n;

Stores the total number of elements in the array.

int a[100];

Declares an integer array capable of holding up to 100 elements.

int getMax()

Finds and returns the largest element in the array to determine the number of digits.

void countSort(int exp)

Sorts array elements based on the significant digit represented by exp (1's, 10's, 100's...).

ArraySort()

Class constructor that initializes object properties when instantiated.

n = 0;

Initializes the array size variable to zero.

void input()

Reads the array size and elements from the user.

for (int exp = 1; ...)

Loops through digit place values (1, 10, 100, ...) until all digits of the maximum number are processed.

void output()

Displays the final sorted array to the console.

ArraySort obj;

Instantiates the ArraySort object and triggers the constructor.

return 0;

Signals successful program execution.

How radix sort works: Radix sort is a non-comparative sorting algorithm. It sorts the numbers digit by digit, starting from the least significant digit (LSD) up to the most significant digit, using a stable sorting algorithm (Counting Sort) as a subroutine for each digit place.