Dutch National Flag Problem - C++ Solution

1. Introduction

The Dutch National Flag Problem is a classic algorithm problem that involves sorting an array containing only three distinct elements. The challenge is to accomplish this in linear time and using constant space, which tests a programmer's ability to implement efficient sorting algorithms with space constraints.

Problem

Given an array containing only elements 0, 1, and 2, the task is to sort the array in ascending order. The solution should be implemented in-place, i.e., without using extra space, and it should have linear time complexity.

2. Solution Steps

1. Initialize three pointers: low, mid, and high. low and mid are set to the beginning of the array, and high is set to the end.

2. Traverse the array using the mid pointer.

3. If mid points to 0, swap it with the element at low and increment both low and mid.

4. If mid points to 1, just increment mid.

5. If mid points to 2, swap it with the element at high and decrement high.

6. Continue this process until mid crosses high.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Utility function to swap two elements in the array
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

// Function to sort the array containing 0s, 1s, and 2s
void sortArray(vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;

    while (mid <= high) {
        switch(nums[mid]) {
            case 0:
                swap(nums[low++], nums[mid++]);
                break;
            case 1:
                mid++;
                break;
            case 2:
                swap(nums[mid], nums[high--]);
                break;
        }
    }
}

int main() {
    vector<int> nums = {0, 1, 2, 2, 1, 0, 0, 2, 0, 1, 1, 0};
    sortArray(nums);

    // Print the sorted array
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Output:

0 0 0 0 0 1 1 1 1 2 2 2

Explanation:

The program implements the Dutch National Flag algorithm to sort the array. It uses three pointers: low for 0s, mid for 1s, and high for 2s. 

By swapping elements based on the value at the mid pointer and adjusting the pointers accordingly, the array is sorted in-place. 

This method ensures linear time complexity and constant space usage, making it an efficient solution for sorting arrays with a limited set of distinct elements.