Radix Sort Analysis

Hi everyone, inside this article we will see the concept about Radix Sort Analysis.

Radix Sort is a non-comparative sorting algorithm that sorts data by grouping the individual digits of the numbers and sorting them in a specific order, starting from the least significant digit to the most significant digit. This sorting technique is also called bucket sort or digital sort.

How Algorithm of Radix Sort works?

The radix sort algorithm works as follows:

1. Determine the maximum number of digits (d) among the numbers to be sorted.
2. For each digit, starting from the least significant digit to the most significant digit, do the following: a. Initialize the count array with all zeros. b. Count the number of occurrences of each digit in the current digit position by iterating through the input array. c. Modify the count array to show the cumulative number of occurrences of each digit. d. Rearrange the input array based on the count array and the current digit position.
3. After processing all digits, the array will be sorted.

The algorithm for Radix Sort can be described using the following pseudocode:

radixSort(arr, n):
    max_element = getMax(arr, n)
    
    # Perform counting sort for every digit
    exp = 1
    while max_element / exp > 0:
        countingSort(arr, n, exp)
        exp *= 10

getMax(arr, n):
    max_element = arr[0]
    for i in range(1, n):
        if arr[i] > max_element:
            max_element = arr[i]
    return max_element

countingSort(arr, n, exp):
    output = [0] * n
    count = [0] * 10
    
    # Store count of occurrences in count[]
    for i in range(0, n):
        index = arr[i] / exp
        count[int(index % 10)] += 1
 
    # Change count[i] so that count[i] now contains actual position of this digit in output[]
    for i in range(1, 10):
        count[i] += count[i - 1]
 
    # Build the output array
    i = n - 1
    while i >= 0:
        index = arr[i] / exp
        output[count[int(index % 10)] - 1] = arr[i]
        count[int(index % 10)] -= 1
        i -= 1
 
    # Copy the output array to arr[], so that arr[] now contains sorted numbers according to current digit
    for i in range(0, len(arr)):
        arr[i] = output[i]

The radixSort function takes an array arr of length n as input and sorts it using radix sort. It first calls the getMax function to determine the maximum element in the array. It then iterates through each digit of the maximum element using the exp variable, calling the countingSort function for each digit.

The getMax function simply iterates through the array to find the maximum element and returns it.

The countingSort function performs counting sort on the array arr with length n using the current digit represented by the exp variable. It first initializes an output array output and a count array count. It then iterates through the array to count the number of occurrences of each digit, storing the count in the count array.

Next, it modifies the count array so that each element represents the starting index of that digit in the output array. It then builds the output array by iterating through the input array backwards, placing each element in its correct position in the output array based on the count of its digit.

Finally, it copies the sorted output array back into the original arr array, completing the sort for the current digit.

Overall, the algorithm performs counting sort on each digit of the input numbers, resulting in a sorted array.

A Basic Example of Radix Sort with Steps

Here’s an example of how Radix Sort works:

For example, let’s say we have an array of integers: [170, 45, 75, 90, 802, 24, 2, 66].

1. The maximum number of digits is 3.
2. Starting from the least significant digit to the most significant digit, we do the following: a. Initialize the count array with all zeros: count[] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]. b. Count the number of occurrences of each digit in the current digit position:
   • For the first pass (the least significant digit), we count the number of occurrences of each digit in the one’s place:
     • count[] = [2, 1, 1, 0, 1, 0, 0, 1, 0, 1]. c. Modify the count array to show the cumulative number of occurrences of each digit:
   • count[] = [2, 3, 4, 4, 5, 5, 5, 6, 6, 7]. d. Rearrange the input array based on the count array and the current digit position:
   • After the first pass, the array becomes: [170, 90, 802, 2, 24, 45, 75, 66]. e. Repeat steps b-d for the second pass (the tens place) and the third pass (the hundreds place) to get the sorted array: [2, 24, 45, 66, 75, 90, 170, 802].

Radix sort is an efficient sorting algorithm that can sort numbers with large ranges and multiple digits. The time complexity of radix sort is O(d * (n + b)), where n is the number of elements in the array, d is the number of digits in the maximum number, and b is the base of the number system used (usually 10). However, radix sort requires extra space to store the count array and the output array, which can be a disadvantage for large datasets.

Example Code

Here’s a basic C++ program for Radix Sort:

#include <iostream>
using namespace std;

// A utility function to get the 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];
  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
  for (int exp = 1; m / exp > 0; exp *= 10)
    countSort(arr, n, exp);
}

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

// The main function
int main()
{
  int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
  int n = sizeof(arr) / sizeof(arr[0]);
  radixSort(arr, n);
  cout << "Sorted array: \n";
  printArray(arr, n);
  return 0;
}

The above program will output:

Sorted array: 
2 24 45 66 75 90 170 802

This program sorts an array of integers using the Radix Sort algorithm. The getMax() function finds the maximum element in the array, which is used to determine the number of digits in the largest number. The countSort() function performs the counting sort on a specific digit (specified by the exp parameter) and the radixSort() function repeatedly calls countSort() for each digit, starting with the least significant digit and working up to the most significant digit. The printArray() function is a utility function used to print the sorted array.

Complexity Analysis of Radix Sort

The time complexity of radix sort depends on the number of digits in the maximum element of the input array. If the maximum element has k digits, then radix sort takes O(kn) time, where n is the number of elements in the input array.

Since radix sort uses a stable sorting algorithm as a subroutine, such as counting sort or bucket sort, the time complexity of these subroutines also contributes to the overall time complexity of radix sort. For example, if counting sort is used as a subroutine and takes O(n+k) time, where k is the range of the input elements, then the overall time complexity of radix sort becomes O(k(n+k)).

Radix sort has a linear time complexity when k is a constant or smaller than log(n), making it faster than comparison-based sorting algorithms such as quicksort and merge sort in these cases. However, radix sort requires additional space proportional to the size of the input array, making it less space-efficient than some other sorting algorithms.

Where is the Radix sort algorithm used?

Radix sort is primarily used when the keys in the dataset to be sorted are of fixed length, and there are a large number of keys that share the same length. Some examples of where Radix sort is used include:

1. Sorting telephone numbers or social security numbers, where each number has a fixed length.
2. Sorting fixed-length strings in a database or file system.
3. Sorting financial transaction data, where each record has a fixed number of digits representing the transaction amount.
4. Sorting IP addresses in network routing tables.

Overall, Radix sort is a useful algorithm for applications where there is a large dataset with keys of fixed length and where the keys can be easily broken down into digits or characters.

Advantages of Radix Sort:

• Radix sort is a stable sort, meaning it preserves the relative order of elements with equal keys.
• It is efficient when the range of values is small, making it faster than comparison-based sorting algorithms in some cases.
• Radix sort is easy to implement and has a predictable O(nk) time complexity, where n is the number of elements and k is the number of digits or bits required to represent the maximum value.

Disadvantages of Radix Sort:

• Radix sort requires extra memory to store the buckets and output array, which can be a limitation for large data sets.
• It is not efficient when the range of values is large, as it requires many iterations over the input data.
• Radix sort has a higher constant factor than some comparison-based sorting algorithms, which can make it slower for small data sets.

We hope this article helped you to understand Radix Sort Analysis in a very detailed way.

Online Web Tutor invites you to try Skillshike! Learn CakePHP, Laravel, CodeIgniter, Node Js, MySQL, Authentication, RESTful Web Services, etc into a depth level. Master the Coding Skills to Become an Expert in PHP Web Development. So, Search your favourite course and enroll now.

If you liked this article, then please subscribe to our YouTube Channel for PHP & it’s framework, WordPress, Node Js video tutorials. You can also find us on Twitter and Facebook.