DSA Radix Sort

Welcome to TheCodingCollege.com, your go-to platform for mastering Data Structures and Algorithms (DSA). In this post, we delve into Radix Sort, an efficient, non-comparison-based sorting algorithm that’s perfect for sorting integers with multiple digits.

What is Radix Sort?

Radix Sort is a sorting algorithm that sorts numbers by processing their digits one place at a time, starting from the least significant digit (LSD) to the most significant digit (MSD). It leverages a stable sorting algorithm, like Counting Sort, to sort individual digits, ensuring that the overall sorting is accurate.

Radix Sort is particularly effective for large datasets with integers or strings where the range of values is constrained.

How Does Radix Sort Work?

1. Determine the Maximum Value: Identify the largest number in the array to know the maximum number of digits.
2. Sort by Digits: Perform sorting digit by digit, starting from the least significant digit (unit place) and progressing to the most significant digit.
3. Stable Sorting: Use a stable sorting algorithm like Counting Sort for each digit to preserve the order of numbers with equal digit values.

Steps in Radix Sort

Let’s sort the array [170, 45, 75, 90, 802, 24, 2, 66]:

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

1. Determine Maximum Value:
   • Maximum = 802
   • Number of digits = 3
2. Sort by Least Significant Digit (LSD):
   • Counting Sort by units place: [802, 2, 24, 45, 75, 66, 170, 90].
3. Sort by Tens Place:
   • Counting Sort by tens place: [802, 2, 24, 45, 66, 75, 170, 90].
4. Sort by Hundreds Place:
   • Counting Sort by hundreds place: [2, 24, 45, 66, 75, 90, 170, 802].

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

Radix Sort Code Implementation

Python Code:

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

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

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

    # Build output array
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1

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

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

# Example usage
array = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(array)
print("Sorted Array:", array)

Output:

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

Java Code:

import java.util.Arrays;

class RadixSort {
    static void countingSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];

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

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

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

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

    static void radixSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();
        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};
        radixSort(arr);
        System.out.println("Sorted Array: " + Arrays.toString(arr));
    }
}

Time and Space Complexity

Advantages and Disadvantages of Radix Sort

Advantages

1. Efficient for Integers: Particularly effective for integers and fixed-length strings.
2. Stable Sorting: Maintains the relative order of equal elements.
3. Non-Comparison-Based: Faster for specific cases compared to comparison-based sorting algorithms.

Disadvantages

1. Range Limitation: Performance depends on the number of digits.
2. Space Requirement: Requires additional space for counting and output arrays.
3. Not In-Place: Uses extra memory during execution.

Applications of Radix Sort

1. Sorting Large Integers: Commonly used in financial systems.
2. Sorting Fixed-Length Strings: Effective for strings with uniform lengths, like ZIP codes.
3. Digital Image Processing: Useful in applications requiring pixel value sorting.

Comparison with Other Sorting Algorithms

Conclusion

Radix Sort is an excellent choice when dealing with datasets where the range of digits is manageable. While it requires more space and multiple passes, its efficiency for large, uniformly distributed datasets makes it a vital part of your DSA toolbox.

Learn more about sorting algorithms and DSA concepts at TheCodingCollege.com, where knowledge meets clarity!