Radix Sort – Sorting Algorithm

Radix Sort

Radix Sort is a non-comparison-based sorting algorithm that works by sorting digits in a multi-digit number starting from the least significant digit (LSD) to the most significant digit (MSD). It is efficient for sorting integers or strings when the range of digits or characters is small.

---

1. How it Works

1. Identify the Maximum Number of Digits: Find the maximum number of digits in the largest element in the dataset.
2. Sort by Digits:
   • Start from the least significant digit (rightmost digit).
   • Use a stable sorting algorithm (like Counting Sort) to sort elements based on the current digit.
   • Move to the next significant digit (leftward) and repeat until all digits have been processed.

---

2. Characteristics

• Time Complexity:
  • O(d × (n + k)), where:
    • d: Number of digits in the largest number
    • n: Number of elements in the array
    • k: Range of the digit (typically 0–9 for decimal numbers)
• Space Complexity: O(n + k) (additional space for counting and output arrays)
• Stable Sorting: Radix Sort is stable, meaning it preserves the relative order of equal elements.
• Limitations:
  • Only applicable to data that can be digitized (e.g., integers or fixed-length strings).
  • Inefficient for very large datasets with a large number of digits.

---

3. Steps

1. Find the Maximum Value: Determine the number of digits in the largest value in the array.
2. Iterate Through Digits:
   • Sort elements based on each digit, starting from the least significant digit to the most significant digit.
3. Output the Sorted Array: After processing all digits, the array will be sorted.

---

4. Example

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

1. Sort by Units Place:
   • After sorting by the rightmost digit: [170, 802, 2, 24, 45, 75, 66, 90]
2. Sort by Tens Place:
   • After sorting by the second-rightmost digit: [802, 2, 24, 45, 66, 170, 75, 90]
3. Sort by Hundreds Place:
   • After sorting by the leftmost digit: [2, 24, 45, 66, 75, 90, 170, 802]

Final Sorted Array: [2, 24, 45, 66, 75, 90, 170, 802]

---

5. Pros and Cons

Advantages:

1. Linear Complexity: Efficient for sorting large datasets with small digits.
2. Non-comparison-based: Avoids the overhead of comparing elements directly.

Disadvantages:

1. Extra Space: Requires additional memory for intermediate steps.
2. Limited Applicability: Only suitable for numeric or fixed-format data.

---

6. Java Implementation

import java.util.Arrays;

public class RadixSort {

    // Method to get the maximum value in the array
    private static int getMax(int[] arr) {
        int max = arr[0];
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }

    // Counting sort based on the digit represented by exp
    private static void countingSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10]; // Digits range from 0-9

        // Count occurrences of digits
        for (int num : arr) {
            count[(num / exp) % 10]++;
        }

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

        // Place elements into the output array in sorted order
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }

        // Copy sorted values back to the original array
        System.arraycopy(output, 0, arr, 0, n);
    }

    // Main Radix Sort method
    public static void radixSort(int[] arr) {
        int max = getMax(arr);

        // Perform counting sort for each digit (exp: 1, 10, 100, ...)
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSort(arr, exp);
        }
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        System.out.println("Original Array: " + Arrays.toString(arr));

        radixSort(arr);

        System.out.println("Sorted Array: " + Arrays.toString(arr));
    }
}

---

7. Python Implementation

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10  # Digits range from 0-9

    # Count occurrences of digits
    for num in arr:
        index = (num // exp) % 10
        count[index] += 1

    # Compute cumulative count
    for i in range(1, 10):
        count[i] += count[i - 1]

    # Place elements into the output array in sorted order
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1

    # Copy sorted values back to the original array
    for i in range(n):
        arr[i] = output[i]


def radix_sort(arr):
    # Find the maximum value in the array
    max_val = max(arr)

    # Perform counting sort for each digit (exp: 1, 10, 100, ...)
    exp = 1
    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10


# Example usage
if __name__ == "__main__":
    arr = [170, 45, 75, 90, 802, 24, 2, 66]
    print("Original Array:", arr)

    radix_sort(arr)

    print("Sorted Array:", arr)

---

8. When to Use Radix Sort

1. Large Datasets with Small Digits:
   • Works well when the range of digits is limited.
2. Integer Sorting:
   • Particularly effective for integer sorting as it avoids direct comparisons.
3. Applications in Strings:
   • Can be adapted for string sorting based on character positions.

Radix Sort is a powerful tool for specific scenarios, offering an efficient alternative to traditional comparison-based algorithms.