Radix Sort Algorithm

Radix Sort Algorithm

Radix Sort is a non-comparative integer sorting algorithm that sorts numbers by processing individual digits. It works by sorting the elements based on their individual digits starting from the least significant digit (LSD) to the most significant digit (MSD) or vice versa. Radix Sort is particularly efficient for sorting integers or strings when the number of digits (or the number of characters in the strings) is relatively small compared to the number of items to be sorted.

Radix Sort uses a stable sorting algorithm (like Counting Sort or Bucket Sort) as a subroutine to sort the digits of the numbers. This allows Radix Sort to sort the entire array in O(nk) time, where n is the number of elements in the array and k is the number of digits in the largest number.

How Radix Sort Works

Radix Sort operates by repeatedly sorting the elements according to individual digits. Here's a step-by-step breakdown of the process:

1. Identify the Maximum Element: First, we determine the maximum number in the array to find out the number of digits (k) in the largest number. This will guide the number of passes the algorithm will make.

2. Sort by Each Digit: Starting with the least significant digit (LSD), the algorithm sorts the numbers based on that digit. After sorting based on the least significant digit, we move to the next more significant digit, and so on, until we have processed all the digits.

3. Stable Sorting: A stable sorting algorithm (like Counting Sort) is used to sort the numbers based on each digit. A stable sort preserves the relative order of equal elements, which is essential for Radix Sort to work correctly.

4. Repeat: This process is repeated for each digit, from the least significant to the most significant, until all digits have been processed.

Steps of Radix Sort

Let’s break down the algorithm into steps:

1. Find the Maximum Number in the array.
2. Sort by Least Significant Digit (LSD) using a stable sorting algorithm like Counting Sort.
3. Move to the next digit and repeat the process until the most significant digit is processed.
4. After processing all the digits, the array is sorted.

Radix Sort Pseudocode

// Function to perform counting sort based on the digit represented by exp
void countingSortByDigit(int arr[], int n, int exp) {
    int output[n];  // Output array to store sorted numbers
    int count[10] = {0};  // Count array to store frequency of digits (0-9)

    // Store count of occurrences of digits in count[]
    for (int i = 0; i < n; i++) {
        count[(arr[i] / exp) % 10]++;
    }

    // Change count[i] to contain the actual position of this digit in output[]
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

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

    // Copy the sorted numbers into the original array
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// Main function to implement Radix Sort
void radixSort(int arr[], int n) {
    // Find the maximum number to know the number of digits
    int max = *max_element(arr, arr + n);

    // Do counting sort for every digit. The exp is 10^i where i is the current digit.
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSortByDigit(arr, n, exp);
    }
}

Example of Radix Sort

Let’s walk through an example of how Radix Sort works:

Suppose we have the following array:

arr = [170, 45, 75, 90, 802, 24, 2, 66]

Step 1: Find the Maximum Number

The largest number in the array is 802, which has 3 digits.

Step 2: Sort by Least Significant Digit (LSD)

• First, we sort the array based on the units place (least significant digit). We use Counting Sort to sort based on this digit.

  • Digits in the units place are: 0, 5, 5, 0, 2, 4, 2, 6

  After sorting by the units digit, the array becomes:

  arr = [170, 90, 802, 2, 24, 45, 75, 66]
  

Step 3: Sort by the Next Digit (Tens Place)

• Next, we sort based on the tens place.

  • Digits in the tens place are: 7, 9, 0, 0, 2, 4, 7, 6

  After sorting by the tens digit, the array becomes:

  arr = [802, 2, 24, 45, 66, 170, 75, 90]
  

Step 4: Sort by the Most Significant Digit (Hundreds Place)

• Finally, we sort based on the hundreds place.

  • Digits in the hundreds place are: 8, 0, 0, 0, 0, 1, 0, 0

  After sorting by the hundreds digit, the array becomes:

  arr = [2, 24, 45, 66, 75, 90, 170, 802]
  

Now, the array is sorted!

Time Complexity of Radix Sort

The time complexity of Radix Sort depends on two factors:

1. n: The number of elements in the array.
2. k: The number of digits in the largest number.

The time complexity can be expressed as:

• O(n * k)

Where n is the number of elements and k is the number of digits in the largest number. The value of k is typically small compared to n, which makes Radix Sort efficient for sorting large datasets with relatively small key sizes (e.g., integers or fixed-length strings).

Breakdown of Time Complexity

1. Counting Sort: Sorting the elements based on each digit (using Counting Sort) takes O(n) time.
2. Digits to Process: We process each digit of each number, and there are k digits in the largest number. So, we perform k iterations of sorting.

Thus, the overall time complexity is O(n * k).

Space Complexity of Radix Sort

The space complexity of Radix Sort is mainly determined by the space needed for the output array and the count array used in Counting Sort. Since both are proportional to the number of elements n, the space complexity is:

• O(n + k)

Where n is the number of elements and k is the base (usually 10, for decimal numbers). This makes the space complexity linear in terms of the number of elements.

Advantages of Radix Sort

1. Efficient for Large Data: Radix Sort can be faster than comparison-based sorting algorithms like Merge Sort or Quick Sort for datasets with small integer keys or fixed-length strings.
2. Linear Time Complexity: When the number of digits (k) is small relative to the number of elements (n), the time complexity can approach O(n), making Radix Sort very efficient.
3. Non-Comparative: Radix Sort doesn’t compare elements directly, which makes it different from comparison-based sorting algorithms.

Disadvantages of Radix Sort

1. Requires a Fixed Range: Radix Sort is not suitable for all data types. It works well for integers or strings but might not be appropriate for complex data structures.
2. Space Complexity: Radix Sort requires additional space for storing counts and output arrays, making its space complexity higher than in-place algorithms like Quick Sort or Heap Sort.
3. Not Stable in All Cases: Radix Sort needs to use a stable sub-sorting algorithm (like Counting Sort) to ensure stability. If a non-stable sort is used, it can break the order of elements with the same key.

Use Cases of Radix Sort

• Sorting Large Numbers: Radix Sort is ideal for sorting large datasets of integers or strings when the keys have a fixed size or small digit range.
• Fixed-Length Strings: It can be used for sorting fixed-length strings (e.g., sorting strings of length 3).
• When Comparison-Based Sorting is Inefficient: For datasets where the key size is large, comparison-based sorting might take longer. Radix Sort can be a better choice when key sizes are small.

Conclusion

Radix Sort is an efficient sorting algorithm for sorting integers or fixed-length strings, especially when the number of digits is small compared to the number of elements. It operates by sorting elements based on individual digits and using a stable sub-sorting algorithm (like Counting Sort). With a time complexity