radix_sort.cpp

/*
                            Radix Sort
1. Identify the maximum number: Find the maximum number in the given list. This is necessary to determine the number of digits we need to consider 
during the sorting process.

2. Perform counting sort for each digit position: Starting from the least significant digit (rightmost digit), perform the following steps for each 
digit position, moving towards the most significant digit (leftmost digit):
a. Create a count array: Create a count array of size 10 (to represent digits 0-9) and initialize all elements to 0. This count array will be used 
to store the frequency of each digit at the current position.
b. Count the frequencies: Iterate through the list of numbers and count the frequency of each digit at the current position. For example, if the 
current digit position is the units place, count the frequency of each digit from 0 to 9.
c. Update the count array: Modify the count array such that each element represents the cumulative count of digits up to that index. This step 
ensures that the count array contains the correct positions for each digit in the sorted order.
d. Distribute the numbers: Iterate through the list of numbers again, and for each number, find its digit at the current position. Use the count 
array to determine the correct position of the number in the output array and place it there. After placing the number, decrement the count for 
that digit in the count array.
e. Collect the numbers: After distributing all the numbers, collect them back into the original array. The array will now be partially sorted 
based on the current digit position.

3. Repeat the counting sort for the next digit position: After collecting the numbers based on the least significant digit, move to the next digit 
position (towards the left) and repeat steps 2a to 2e for that digit. Continue this process until all the digits have been processed, from the least 
significant digit to the most significant digit.

4. Final sorted list: After completing the counting sort process for all digit positions, you will have a fully sorted list of numbers.

Here's an example to illustrate the process:

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

# 1. First iteration (Least significant digit - rightmost digit):
    # Create the count array: [0, 2, 1, 1, 0, 1, 0, 0, 0, 1]
    # Update the count array: [0, 2, 3, 4, 4, 5, 5, 5, 5, 6]
    # Distribute the numbers: [802, 2, 24, 45, 75, 170, 90, 66]
    # Collect the numbers: [802, 2, 24, 45, 75, 170, 90, 66]

# 2. Second iteration (Next least significant digit):
    # Create the count array: [1, 2, 1, 1, 1, 1, 0, 0, 0, 1]
    # Update the count array: [1, 3, 4, 5, 6, 7, 7, 7, 7, 8]
    # Distribute the numbers: [802, 2, 24, 45, 66, 75, 90, 170]
    # Collect the numbers: [802, 2, 24, 45, 66, 75, 90, 170]

# 3. Third iteration (Most significant digit):
    # Create the count array: [1, 1, 1, 1, 2, 2, 1, 0, 0, 0]
    # Update the count array: [1, 2, 3, 4, 6, 8, 9, 9, 9, 9]
    # Distribute the numbers: [2, 24, 45, 66, 75, 90, 170, 802]
    # Collect the numbers: [2, 24, 45, 66, 75, 90, 170, 802]

# The final sorted list is [2, 24, 45, 66, 75, 90, 170, 802].

# Radix sort using counting sort works by sorting the numbers digit by digit, from the least significant digit to the most significant digit. 
# The counting sort process distributes and collects the numbers based on each digit position, ensuring that the numbers are correctly ordered at 
# each iteration. By repeating this process for each digit, the algorithm achieves a fully sorted list without the need for explicit element comparisons.

*/

#include <iostream>
using namespace std;

// Function to get maximum value in arr[]
int getMax(int arr[], int n)
{
	int mx = arr[0];
	for (int i = 1; i < n; i++)
		if (arr[i] > mx)
			mx = arr[i];
	return mx;
}

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

	// Store count of occurrences in count[]
	for (i = 0; i < n; i++)
		count[(arr[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[(arr[i] / exp) % 10] - 1] = arr[i];
		count[(arr[i] / exp) % 10]--;
	}

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

// The main function to that sorts arr[] of size n using
// Radix Sort
void radixsort(int arr[], int n)
{
	// Find the maximum number to know number of digits
	int m = getMax(arr, n);

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

// Function to print an array
void print(int arr[], int n)
{
	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";
}


int main()
{
	int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 };
	int n = sizeof(arr) / sizeof(arr[0]);
	
	// Function Call
	radixsort(arr, n);
	print(arr, n);
	return 0;
}

// Time Compexity -> O((n+k)*d)
// Space Complexity -> O(n+k)