Radix Sort Algorithm

Radix Sort is a non-comparative sorting algorithm that sorts integers by processing individual digits. It processes the numbers by their digit positions and groups them into "buckets" based on the value of each digit.

How Radix Sort Works

1. Least Significant Digit (LSD) Approach:

   • Start sorting from the least significant digit to the most significant digit.

2. Bucketing Process:

   • Place elements into separate buckets according to the value of the current digit being considered.

3. Sorting Passes:

   • Perform multiple passes through the array, distributing elements into buckets based on each digit.
   • After the last pass, the elements are sorted according to their digits.

4. Completion:

   • Continue the process until the most significant digit is reached, sorting the elements in the array.

Key Features

• Non-Comparative Sort: Radix Sort does not compare elements directly, instead sorting by the value of their digits.

• Linear Time Complexity: It operates in linear time, making it efficient for sorting integers.

Efficiency

• Time Complexity: Radix Sort has a time complexity of O(k * n), where k is the number of digits and n is the number of elements.

• Space Complexity: Radix Sort has a space complexity of O(n + k) since it uses extra space for bucket storage.

Advantages

Radix Sort has several advantages, including:

• Efficiency with Integers: Efficiently sorts integers without direct comparisons.
• Linear Time Complexity: It operates in linear time relative to the number of elements and digits.

Disadvantages

Radix Sort also has some limitations, such as:

• Limited to Integers: Primarily suited for integer values and requires modifications for other data types.
• Memory Consumption: Requires extra space for bucketing, leading to higher space complexity.

Radix Sort Implementation in JavaScript

Here's an example of Radix Sort implemented in JavaScript:

function radixSort(arr) {
    const max = Math.max(...arr);
    for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
        countSort(arr, exp);
    }
    return arr;
}
 
function countSort(arr, exp) {
    const output = new Array(arr.length).fill(0);
    const count = new Array(10).fill(0);
 
    for (let i = 0; i < arr.length; i++) {
        count[Math.floor(arr[i] / exp) % 10]++;
    }
 
    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
 
    for (let i = arr.length - 1; i >= 0; i--) {
        output[count[Math.floor(arr[i] / exp) % 10] - 1] = arr[i];
        count[Math.floor(arr[i] / exp) % 10]--;
    }
 
    for (let i = 0; i < arr.length; i++) {
        arr[i] = output[i];
    }
}
 
const unsortedArray = [170, 45, 75, 90, 802, 24, 2, 66];
const sortedArray = radixSort(unsortedArray);
console.log("Sorted Array:", sortedArray);

In this JavaScript code:

• The radixSort function implements the Radix Sort algorithm by using counting sort for each digit.
• The countSort function performs the counting sort to sort the elements based on their digits.