Sort Colors (Dutch National Flag)

Welcome to our lesson on sorting colors using the Dutch National Flag algorithm! This technique is a variation of the QuickSort algorithm, and it's particularly useful when you need to sort an array of colors. Let's dive in! 🎯

Understanding the Problem

Imagine you have an array of colors, and you want to sort them in a specific order: Red, Blue, and Yellow. This problem can be solved using the Dutch National Flag algorithm, which is a clever and efficient method for sorting colors.

The Algorithm Explained

The Dutch National Flag algorithm is based on the idea that elements in an array are partitioned into three parts:

Left (L) partition: Elements less than a specific pivot (initially the last element)
Right (R) partition: Elements greater than the pivot
Middle (M) partition: Elements equal to the pivot

By repeatedly partitioning the array, we can sort the colors efficiently. Let's see how it works.

Pivot Selection

In our case, we will use the last color as the pivot. If the pivot is Blue, all Reds will go to the left, Blues will be in the middle, and Yellows will go to the right. 💡 Pro Tip: You can also use the median of the three colors as the pivot for better performance.

Partitioning

Starting from the left, compare each color with the pivot. If it's less than the pivot, move it to the left partition. If it's equal to the pivot, move it to the middle partition. If it's greater than the pivot, move it to the right partition.

Recursion

Now, repeat the partitioning process for the left and right partitions. Once the partitions are sorted, merge them to get the final sorted array.

Implementing the Dutch National Flag Algorithm

Here's a simple implementation in Python:

python

def dutch_national_flag(arr):
    low = 0
    high = len(arr) - 1
    pivot = arr[high]

    while low <= high:
        if arr[low] == pivot:
            low += 1
        elif arr[low] < pivot:
            arr[low], arr[high] = arr[high], arr[low]
            high -= 1
        else:
            arr[low], arr[low + 1] = arr[low + 1], arr[low]
            low += 1

    return arr

In this code, we're using the last color as the pivot and comparing each color with it. If it's less than the pivot, we swap the current color with the color at the high position and decrease the high pointer. If it's greater than the pivot, we swap the current color with the next color and increment the low pointer. If it's equal to the pivot, we move to the next color.

Practice Time

Let's test your understanding with a quick quiz!

We hope you enjoyed learning about the Dutch National Flag algorithm! Stay tuned for more exciting lessons on Data Structures and Algorithms. Happy coding! 📝 Note: You can apply this concept to sort arrays of any objects, not just colors.