Sort an Array of 0s, 1s, 2s (Dutch National Flag)

Welcome to a fascinating journey through the world of Data Structures and Algorithms! Today, we'll learn how to sort an array consisting of only 0s, 1s, and 2s, also known as the Dutch National Flag problem.

This problem is a classic example of an in-place, one-pass sorting algorithm that's both easy to understand and practical. Let's dive in!

What is the Dutch National Flag problem?

The Dutch National Flag problem is a sorting problem where you are given an array containing only 0s, 1s, and 2s. The goal is to sort this array in ascending order (0, 1, 2) in a single pass.

Before we dive into the solution, let's understand why we might encounter such a problem in real-world scenarios.

💡 Pro Tip: This problem is useful when dealing with data streams where the data is continuously arriving and you need to sort it as soon as possible.

Solving the Dutch National Flag problem

We'll introduce an algorithm called the "Dutch National Flag Algorithm" to solve this problem. The algorithm works by partitioning the array into three sections:

0s (left)
2s (right)
Unsorted (middle)

We'll then iterate through the unsorted section, swapping elements as necessary to maintain the three sections. Once the unsorted section is empty, the array will be sorted.

Let's see the algorithm in action with a simple example.

📝 Note: Here, we use a variable 'i' to represent the left pointer (starting from the beginning of the array), a variable 'j' to represent the right pointer (starting from the end of the array), and a variable 'k' to represent the middle pointer (initially pointing to the first element).

python

arr = [1, 0, 2, 1, 2, 1, 0]
i = 0
j = len(arr) - 1
k = 0

while k <= j:
    if arr[k] == 0:
        arr[k], arr[i] = arr[i], arr[k]
        i += 1
        k += 1
    elif arr[k] == 2:
        arr[k], arr[j] = arr[j], arr[k]
        j -= 1
    else:
        k += 1

In the above example, we sorted the array [1, 0, 2, 1, 2, 1, 0] to [0, 0, 1, 1, 2, 2, 2].

Advanced Example

Let's consider a larger example to demonstrate the efficiency of the Dutch National Flag algorithm:

python

arr = [1, 0, 2, 0, 2, 1, 0, 2, 1, 0, 2, 1, 0]
i = 0
j = len(arr) - 1
k = 0

while k <= j:
    if arr[k] == 0:
        arr[k], arr[i] = arr[i], arr[k]
        i += 1
        k += 1
    elif arr[k] == 2:
        arr[k], arr[j] = arr[j], arr[k]
        j -= 1
    else:
        k += 1

print(arr)

In the above example, we sorted the array [1, 0, 2, 0, 2, 1, 0, 2, 1, 0, 2, 1, 0] to [0, 0, 0, 1, 1, 1, 2, 2, 2, 2].

🎯 Key Takeaways:

The Dutch National Flag problem is a classic sorting problem involving only 0s, 1s, and 2s.
The problem can be solved using a simple, in-place one-pass algorithm called the Dutch National Flag Algorithm.
The algorithm partitions the array into three sections: 0s (left), 2s (right), and unsorted (middle), and iteratively sorts the array by swapping elements as necessary.
The algorithm is particularly useful for sorting data streams with only 0s, 1s, and 2s.

Happy Coding! 🚀🌟