Sorting Algorithms: Counting Sort - The Sorting Technique That Doesn’t Compare!

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

Hello again, brave coder 👨‍💻. Imagine you're the host of a big Halloween party 🎃, and every guest has come dressed in unique costumes 🧛‍♂️ with ages written on their badges. Your task is to line everyone up, from youngest to oldest, without asking anyone’s age directly. How? That’s when Counting Sort enter the showroom, the sorting hero that organizes without comparison!

Counting Sort is a non-comparison based sorting algorithm, which means it doesn’t line things up by comparing pairs like most other sorts (like Bubble Sort or Quick Sort). Instead, it counts the items and places them in order based on this count.

I’m sure you’re asking: “How the hell it can do that? ”. Don’t worry, I got you! Let’s dive into Counting Sort magic ✨

---

🧠Understanding Counting Sort

Counting Sort works best when sorting a range of integers within a limited set (like ages between 0 and 100). It uses an array to keep track of the count of each value in the input list.

Here's a high-level view of the steps:

1. Count the Elements: For each unique number in the input, count how often it appears.

2. Accumulate Counts: Convert the counts into positions by accumulating counts, which tells us where each number should go.

3. Place the Items in Order: Use the accumulated counts to place items in their sorted position.

Let's break this down with a concrete example!

---

🎮 Game 1: Counting Ages

You have a list of your party guests and their ages:

Guests’ Ages: [3, 2, 3, 4, 3, 1, 0, 2, 4]

Your job is to line everyone up from youngest to oldest without comparing ages. Let’s set up our game board!

- Step 1: Count the Ages

To count how many times each age appears, create a count array. If you know that the ages range from 0 to 4, make an array of zeros for each age :

Count Array: [0, 0, 0, 0, 0]

PS: the array should have “the maximum element in the array plus one“ size:

example: [3, 2, 3, 4, 3, 1, 0, 2, 4] => the max number is 4

4 + 1 = 5 (5 zeros) => count array = [0, 0, 0, 0, 0]

Now, go through the list of ages and update the count array:

• For age 3: increment the third position → [0, 0, 0, 1, 0]

• For age 2: increment the second position → [0, 0, 1, 1, 0]

• And so on...

After counting all ages, your count array will look like this:

Count Array: [1, 1, 2, 3, 2]

This tells us:

• There’s 1 person aged 0,

• 1 person aged 1,

• 2 people aged 2, and so on.

- Step 2: Accumulate the Counts

Now let’s figure out where each age group should start in the final lineup by accumulating counts. Replace each element in the count array with the sum of itself and all previous elements.

Starting with [1, 1, 2, 3, 2]:

1. The first position stays as 1.

2. The second position becomes 1 + 1 = 2.

3. The third becomes 2 + 2 = 4.

4. Fourth becomes 4 + 3 = 7.

5. Last becomes 7 + 2 = 9.

After accumulation, we get:

Count Array: [1, 2, 4, 7, 9]

Each number here tells us the starting position in the sorted order for that age group. For example:

• Age 0 starts at position 1.

• Age 1 starts at position 2, and so forth.

- Step 3: Place in Sorted Order (Line Up the Guests)

Time for the final action! Go back to the original list of ages and place each age in its sorted position using the accumulated counts array.

1. Take the age 3 from the list.

   • Place it at position 7 (from count array), then decrement that position in the count array.

   • Sorted List: [_, _, _, _, _, _, 3, _, _]

2. Move to age 2.

   • Place it at position 4, update the count array (decrement that position).

   • Sorted List: [_, _, _, 2, _, _, 3, _, _]

Repeat for each age. At the end, you’ll get this:

Sorted Ages: [0, 1, 2, 2, 3, 3, 3, 4, 4]

Taraa! You’ve sorted the array without comparing them directly 😉

Counting Sort in Action!

---

👨‍💻Coding Time! YeeeeeY!

function countingSort(arr) {
    // Step 1: Find the maximum value in the array to define the range
    const max = Math.max(...arr);
    
    // Step 2: Initialize a count array with zeros
    const countArray = new Array(max + 1).fill(0);
    
    // Step 3: Count the occurrences of each number in the input array
    for (let num of arr) {
        countArray[num]++;
    }
    
    // Step 4: Accumulate counts to get positions
    for (let i = 1; i < countArray.length; i++) {
        countArray[i] += countArray[i - 1];
    }
    
    // Step 5: Create an output array to store sorted elements
    const output = new Array(arr.length);
    
    // Step 6: Place each element from the array into its sorted position
    for (let i = arr.length - 1; i >= 0; i--) {
        const num = arr[i];
        const position = countArray[num] - 1;
        output[position] = num;
        countArray[num]--;
    }
    
    return output;
}

// Example usage:
const arr = [3, 2, 3, 4, 3, 1, 0, 2, 4];
console.log("Original Array:", arr); // [3, 2, 3, 4, 3, 1, 0, 2, 4]
console.log("Sorted Array:", countingSort(arr)); // [0, 1, 2, 2, 3, 3, 3, 4, 4]

📝 Explanation of Each Step

1. Find the Maximum Value: We need to know the range of numbers in the input array (0 to max) so we can create a countArray that matches this range.

2. Initialize the Count Array: This array, with a length of max + 1, will store the count of each number in the input array.

3. Count Occurrences: We increment the count for each number in the input array. For example, if the input array has three 3s, then countArray[3] will be 3.

4. Accumulate Counts: By adding each element to the previous one, we convert the count array into a positions array. Now countArray[i] tells us where i should be placed in the final sorted array.

5. Create the Output Array: Using the positions from countArray, we place each element from the original array into its sorted position in the output array.

6. Return the Sorted Array: The output array now contains the sorted elements.

⏰ Time Complexity

Counting Sort is O(n + k), where:

• n is the number of elements in the array.

• k is the range of numbers (from 0 to max in this example).

---

🎲 Pros & Cons of Counting Sort

1. Counting Sort is FAST! It’s O(n + k), where n is the number of items and k is the range of numbers (like ages 0 to 100).

2. Stable Sort: Counting Sort keeps duplicates in the original order. If two people have the same age, they’ll stay in their initial order.

3. Memory Usage: It uses extra space for the count array, so it’s best for small ranges!

---

🕹️ Quick Game!

Let’s test your understanding with a quick activity, do it using a pen and paper 📄✏️:

Given the ages [2, 1, 2, 0, 3, 1, 4], try counting, accumulating, and lining them up in order.

Solution:

Did you get [0, 1, 1, 2, 2, 3, 4]? If no, don’t worry, just go back again and read the article carefully. It’s a new concept, so that’s fine to get stuck at the first few tries Boss!

---

🚦 When Should You Use Counting Sort?

Counting Sort is like a specialty tool: incredibly effective, but for certain jobs only! Here are the best situations for putting Counting Sort to work:

1. Small Range of Values: Counting Sort shines when your values are integers in a small range (say, 0 to 100). If you tried Counting Sort on a list with values ranging from 1 to a million, you’d waste memory.

2. Repetitive Data: If you have a lot of duplicates (e.g., ages or scores), Counting Sort can quickly group and sort them without comparing every item.

3. Real-time or Performance-Critical Applications: In cases where performance is critical, and the data is controlled, such as sorting grades or attendance, Counting Sort’s O(n + k) time complexity is unbeatable.

4. Sorting by Multiple Fields: Counting Sort can be used as a stable sorting method in multi-field sorting. For example, in sorting people first by age, then by name (if the ages are the same), Counting Sort preserves the original order, making it useful in these cases.

Examples:

• Age or Score Sorting: Need to quickly sort scores from 0-100 across thousands of students? Counting Sort is quick, accurate, and stable.

• Frequency Distribution: Analyzing the frequency of small-integer datasets, like polling responses (on a scale of 1-10), is perfect for Counting Sort.

• Image Processing: Counting Sort is used to sort color values in images, where there’s a limited range of values for each color channel (like 0-255 for RGB values).

---

🏁 Final Thoughts

Counting Sort isn’t always the best choice, but in cases with small integer ranges or heavy duplication, it’s a speed beast!

So, next time you’re looking at a dataset and notice it’s a small, limited range of numbers, consider Counting Sort and “tfekerni” haha, it may just surprise you with its efficiency and speed!

Now, you’re a pro at counting sort! Don’t forget to use it when it’s the right time!

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!