Radix sort

 

Radix sort:

Understanding Radix Sort: A Linear Sorting Algorithm

Radix Sort is a fascinating and efficient sorting algorithm, especially suitable for sorting integers or strings with fixed-size keys. Unlike traditional comparison-based sorting algorithms like QuickSort or MergeSort, Radix Sort processes elements by their individual digits, achieving linear time complexity under certain conditions.

How Radix Sort Works

Radix Sort sorts elements by distributing them into buckets based on each digit's value. It processes the elements digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD). This method ensures that the elements are sorted in their correct order by the end of the process.

Here's a step-by-step breakdown of how Radix Sort works:

1. Identify the Maximum Number of Digits: Determine the maximum number of digits (d) in the largest number or longest string in the list. This step ensures that the algorithm knows how many passes it needs to make.

2. Sorting by Each Digit: For each digit, from the least significant to the most significant:

   • Distribute the elements into buckets based on the current digit's value.
   • Collect the elements from the buckets and reconstruct the list. This process is repeated for each digit until all digits have been processed.

Example: Radix Sort in Action

Let's illustrate Radix Sort with a simple example. Suppose we want to sort the following list of integers:

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

1. Identify the Maximum Number of Digits: The maximum number in the list is 802, which has 3 digits. So, we need to make 3 passes (one for each digit).

2. First Pass (Least Significant Digit):

   • Distribute the numbers into buckets based on the units place (LSD):

     
     
     0-9 Buckets: [170, 90, 802, 2], [45], [75], [24], [66]
     

   • Reconstruct the list: List = [170, 90, 802, 2, 45, 75, 24, 66]

3. Second Pass (Tens Digit):

   • Distribute the numbers into buckets based on the tens place:

     
     
     0-9 Buckets: [802, 2], [24], [45], [66, 75, 170, 90]
     

   • Reconstruct the list: List = [802, 2, 24, 45, 66, 75, 170, 90]

4. Third Pass (Most Significant Digit):

   • Distribute the numbers into buckets based on the hundreds place:

     
     0-9 Buckets: [2, 24, 45, 66, 75, 90], [170], [802]
     

   • Reconstruct the list: List = [2, 24, 45, 66, 75, 90, 170, 802]

After these passes, the list is sorted in ascending order.

Why Use Radix Sort?

Radix Sort is particularly useful when:

• The range of input values is known and not too large.
• The keys are of fixed size, such as integers or strings of uniform length.
• A stable sorting algorithm is required, as Radix Sort maintains the relative order of elements with equal keys.

This explanation provides a clear and human-readable overview of how Radix Sort operates, including a detailed example to illustrate its process.

Program:

#include <iostream>

using namespace std;

 

// A utility 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)

{

 

    // Output array

    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.

    // 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);

}

 

// A utility function to print an array

void print(int arr[], int n)

{

    for (int i = 0; i < n; i++)

        cout << arr[i] << " ";

}

 

// Driver Code

int main()

{

    int arr[] = { 543, 986, 217, 765, 329 };

    int n = sizeof(arr) / sizeof(arr[0]);

 

    // Function Call

    radixsort(arr, n);

    print(arr, n);

    return 0;

}

 

Output: