Sorting Algorithms: Radix Sort - The Sorting Flash ⚡️

Let's discover another amazing sorting algorithm: Radix Sort!

Hello brave coders👨‍💻, we all agree that sorting numbers from smallest to largest, is a classic programming problem, and Radix Sort is like the super-speed Flash⚡️, that sorts even large lists of numbers quickly! In today’s article, we’ll dive into the world of Radix Sort in a fun and beginner-friendly way, using a step-by-step guide with fun examples and code of course (I know you love this part haha)!

So, without further do, let’s get started! Ala Barakati Lah🙏

❓What is Radix Sort?

Imagine you have a big pile of mail (numbers) 📬 that you need to organize by ZIP code. Radix Sort is like sorting each piece of mail by looking at one digit of the ZIP code at a time (from right to left). It’s a non-comparative sorting algorithm, like the Counting Sort Algorithm that we saw in the previous article, meaning it doesn’t compare numbers directly but groups them based on individual digits! This lets it efficiently handle lots of large numbers with ease!

🎮 Radix Sorting Game Rules

1. Digit-by-Digit Sorting: Start with the rightmost digit (units place), then move left through each digit.

2. Use Buckets: For each digit, create 10 “buckets” (0-9) to hold numbers based on the digit.

3. Iterate Until Sorted: Repeat the sorting process for each digit position until all numbers are organized.

---

📜 Radix Sort Algorithm in Action

Let’s say you have these numbers to sort:

[123, 45, 678, 89, 10]

📌Step 1: Sort by Units Place (Rightmost Digit)

1. Look at the units place (rightmost digit) for each number:

   • 123 ➔ Units digit = 3

   • 45 ➔ Units digit = 5

   • 678 ➔ Units digit = 8

   • 89 ➔ Units digit = 9

   • 10 ➔ Units digit = 0

2. Place each number into its respective bucket (0-9) based on the units’ digit:

   • Bucket 0: [10]

   • Bucket 3: [123]

   • Bucket 5: [45]

   • Bucket 8: [678]

   • Bucket 9: [89]

3. Collect numbers from the buckets in order (0 through 9):

   • After collecting: [10, 123, 45, 678, 89]

Step 1 Result : [10, 123, 45, 678, 89]

📌Step 2: Sort by Tens Place

Array after previous step: [10, 123, 45, 678, 89]

1. Look at the tens place (second digit from the right) for each number:

   • 10 ➔ Tens digit = 1

   • 123 ➔ Tens digit = 2

   • 45 ➔ Tens digit = 4

   • 678 ➔ Tens digit = 7

   • 89 ➔ Tens digit = 8

2. Place each number into its respective bucket based on the tens’ digit:

   • Bucket 1: [10]

   • Bucket 2: [123]

   • Bucket 4: [45]

   • Bucket 7: [678]

   • Bucket 8: [89]

3. Collect numbers from the buckets in order:

   • After collecting: [10, 123, 45, 678, 89]

Step 2 Result : [10, 123, 45, 678, 89]

📌Step 3: Sort by Hundreds Place

Array after previous step: [10, 123, 45, 678, 89]

1. Look at the hundreds place (third digit from the right) for each number. If a number doesn’t have a hundred digit, treat it as 0.

   • 10 ➔ Hundreds’ digit = 0 (since there’s no hundreds’ digit)

   • 123 ➔ Hundreds’ digit = 1

   • 45 ➔ Hundreds’ digit = 0

   • 678 ➔ Hundreds’ digit = 6

   • 89 ➔ Hundreds’ digit = 0

2. Place each number into its respective bucket based on the hundreds’ digit:

   • Bucket 0: [10, 45, 89]

   • Bucket 1: [123]

   • Bucket 6: [678]

3. Collect numbers from the buckets in order:

   • After collecting: [10, 45, 89, 123, 678]

Final sorted result 🥳️: [10, 45, 89, 123, 678]

---

Now that we understand the theory behind Radix Sort Algorithm, let’s switch to the funny part! The coding you all have been waiting for 👨‍💻

👨‍💻Step-by-Step Coding Radix Sort From Scratch

Here’s a beginner-friendly, step-by-step code to implement Radix Sort. Let’s break it down!

📌Step 1: Finding the Maximum Digits (getMaxDigits)

Before we begin sorting, we need to know how many digits the largest number has. This tells us how many times to run our sorting function.

const getMaxDigits = (arr) => {
    let max = Math.max(...arr);
    return max.toString().length;
};

• Example: If our array is [123, 45, 678, 89, 10], the largest number is 678, which has 3 digits.

📌Step 2: Getting a Digit at a Specific Place (getDigit)

This helper function pulls out the digit at the specified place. For example, the units place for 123 is 3, and for the tens place, it’s 2.

const getDigit = (num, place) => {
    return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
};

• Example: getDigit(123, 0) would give 3, getDigit(123, 1) would give 2, and so on.

📌Step 3: Sorting by Each Digit (countingSortByDigit)

Now, we create buckets to group numbers by the current digit place (0-9).

const countingSortByDigit = (arr, place) => {
    const buckets = Array.from({ length: 10 }, () => []);
    
    arr.forEach(num => {
        const digit = getDigit(num, place);
        buckets[digit].push(num);
    });
    
    return [].concat(...buckets);
};

• Example: When sorting [123, 45, 678, 89, 10] by the units place:

  • Bucket 0: [10]

  • Bucket 3: [123]

  • Bucket 5: [45]

  • Bucket 8: [678, 89]

After collecting these, we move on to the next digit (tens place).

📌Step 4: Putting It All Together

In the main function, we run the sorting process for each digit place up to the maximum number of digits. After each pass, we get closer to a fully sorted array!

const maxDigits = getMaxDigits(arr);
for (let place = 0; place < maxDigits; place++) {
    arr = countingSortByDigit(arr, place);
}
return arr;

Each pass organizes the array by one more digit position, starting from the units’ place and moving left. By the time we finish all passes, we have a fully sorted list!

📌Last Step (optional): Full Radix Sort Code in one function!

function radixSort(arr) {
    
    const getMaxDigits = (arr) => {
        let max = Math.max(...arr);
        return max.toString().length;
    };

    const getDigit = (num, place) => {
        return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
    };

    const countingSortByDigit = (arr, place) => {
        const buckets = Array.from({ length: 10 }, () => []);
        
        arr.forEach(num => {
            const digit = getDigit(num, place);
            buckets[digit].push(num);
        });
        
        return [].concat(...buckets);
    };

    const maxDigits = getMaxDigits(arr);
    
    for (let place = 0; place < maxDigits; place++) {
        arr = countingSortByDigit(arr, place);
    }

    return arr;
}

🎉 Testing It Out!

Let’s see if our function really works!

const numbers = [123, 45, 678, 89, 10];
console.log("Sorted:", radixSort(numbers));

If everything’s right, the output will be:

Sorted: [10, 45, 89, 123, 678]

---

🎈 Why Radix Sort is Awesome

• It’s Fast for Big Lists: Radix Sort is great for sorting large lists of integers quickly.

• No Comparisons: Unlike many sorting algorithms, Radix Sort doesn’t rely on comparisons, making it faster for certain types of data.

• Simple with Large Numbers: When handling big numbers, Radix Sort shines as a fast, easy solution.

---

📊 Time Complexity of Radix Sort

Radix Sort's time complexity depends on two main factors:

1. The number of digits (d) in the largest number in the list.

2. The number of elements (n) in the array.

The total time complexity can be broken down as:

\(O(d⋅(n+b))\)

• d = The number of digits in the largest number (this is typically constant for fixed-width integers).

• n = Number of elements in the list.

• b = Base used for each digit (like 10 for decimal).

---

🧠 Space Complexity of Radix Sort

Radix Sort requires extra space for buckets to store elements temporarily while sorting by each digit. So, the space complexity is O(n + b), where:

• n is the number of elements.

• b is the base (10 if using decimal).

This extra memory usage can become substantial for very large arrays or large values of b. Thus, Radix Sort is a space-intensive algorithm compared to simple sorts like Bubble Sort or even Quick Sort, which can be implemented with minimal extra memory.

---

🎯 Where to Use Radix Sort

Radix Sort is best for large lists of non-negative integers or fixed-width strings, where:

1. You have a lot of elements (n), and each has a limited range of digits.

2. You want efficient, stable sorting without comparisons, making Radix Sort ideal for cases where other methods (like Quick Sort or Merge Sort) might be slower.

3. Uniform length or fixed-width data (e.g., ZIP codes, phone numbers, binary integers) works well since the digit length won’t vary dramatically.

🚫 Where NOT to Use Radix Sort

Radix Sort isn’t suitable for every scenario! Like:

1. Sorting Floating-Point Numbers: For floating-point numbers, algorithms like Merge Sort or Quick Sort are more suitable.

2. Lists with Very Large Digit Ranges: When numbers have extremely high digit counts (like in scientific computing), Radix Sort can get bogged down because d becomes very large.

3. Variable-Length Strings: Radix Sort is less efficient for strings of different lengths, as it’s designed to handle uniform digit (or length) sizes across all elements.

4. Limited Space: If you’re dealing with space constraints, Radix Sort may be costly due to the additional space required for buckets. Quick Sort or Heap Sort might be more suitable in low-memory environments.

---

🏆 Summary

• Radix Sort is ideal when dealing with large lists of integers or fixed-width strings, especially when the range of digits is small.

• It’s generally faster than many comparison-based sorts in these cases but needs extra memory and performs less efficiently for data with high variability in digit length or with decimals.

• For general-purpose sorting or cases with memory constraints, consider Quick Sort or Merge Sort instead.

That’s all for today’s article, I hope that I explained this topic, in an easy, beginner-friendly as possible way!

Good luck, see you in the next article 👋

🔔 Don't forget to subscribe to my blog and YouTube channel to stay updated with all the latest content!