Dutch National Flag problem - sorting an array of 0s 1s 2s

The Dutch National Flag problem, which is also simplified as sorting an array containing 0s 1s 2s, is a classic computer science problem proposed by Edsger Dijkstra, a renowned Dutch computer scientist. Dijkstra named the algorithm after the tricolor flag of the Netherlands, which consists of three horizontal stripes in red, white, and blue. This problem is also referred to as “Sort colors” or “Tricolor sorting” and can be related to sorting an array containing only 3 distinct elements.

Problem Statement

Given an array containing only three distinct elements (or three distinct categories of elements), sort the array in-place such that all occurrences of one element are together, followed by all occurrences of the second element, and then all occurrences of the third element.

Example input:

Let’s consider an array of integers containing only 0s, 1s, and 2s:

[1, 0, 2, 1, 0, 1, 2, 2, 0, 1]

Expected output:

[0, 0, 0, 1, 1, 1, 1, 2, 2, 2]

In this sorted output, all 0s come first, followed by all 1s, and then all 2s.

Relation With Dutch National Flag

The problem of sorting an array containing only 0s, 1s, and 2s is often referred to as the “Dutch National Flag” problem due to its connection with the colors of the Dutch flag. It consists of three horizontal stripes: red at the top, white in the middle, and blue at the bottom. Below is how the dutch national flag looks:

If we associate 0 with red, 1 with white, and 2 with blue, the problem of sorting these numbers becomes analogous to arranging the colors of the Dutch flag in the correct order. Just as the Dutch flag has distinct sections for each color, the sorting algorithm aims to create three distinct sections in the array: one for 0s, one for 1s, and one for 2s. Below is how the example array looks after coloring:

Solving with Sorting Algorithms

We can use any standard sorting algorithms such as Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, or Quick Sort to group and move all 0s to the beginning, followed by all 1s and then all 2s. However, it’s important to note that while these methods will work, they are not specifically optimized for this particular problem.

The time complexity of these standard sorting algorithms varies depending on the chosen method. For instance, simpler algorithms like Bubble Sort, Insertion Sort, and Selection Sort typically have a time complexity of O(n^2), where n is the number of elements in the array. More efficient algorithms like Merge Sort and Quick Sort offer better performance with a time complexity of O(n log n). Similarly, the space complexity differs among these algorithms, ranging from O(1) for in-place sorting methods to O(n) for algorithms that require additional memory proportional to the input size. While these general-purpose sorting algorithms will get the job done, there are more efficient approaches specifically tailored to sorting arrays containing elements of only 3 distinct values.

Click here to learn more about different sorting techniques

Counting Approach (Two Pass Solution)

The main idea behind the Counting Approach for sorting 0s, 1s, and 2s is to count the occurrences of each number in the array, then use that information to reconstruct the sorted array. This method is faster than traditional sorting algorithms for this specific case, as it only requires two passes through the array.

Below is the algorithm:

1. Initialize three variables: zeroes_count, ones_count, and twos_count to keep track of the number of0s, 1s, and 2s in the array.
2. Traverse the entire array once, incrementing the appropriate count variable for each element encountered.
3. Reset a pointer to the beginning of the array.
4. Fill the first zeroes_count positions of the array with 0s.
5. Fill the next ones_count positions of the array with 1s.
6. Fill the remaining twos_count positions of the array with 2s.
7. The array is now sorted with all 0s at the beginning, followed by all 1s, and then all 2s at the end.

This approach is highly efficient, with a time complexity of O(n) and a space complexity of O(1). It requires only two passes through the array - one for counting and one for filling. This makes it faster than traditional sorting algorithms for this specific case.

However, it’s important to note that this method has limitations. It only works for sorting a fixed set of distinct values (in this case, 0s, 1s, and 2s). If the array contains unique objects and if sorting needs to be done based on a particular attribute of each object, this approach would not be suitable. In such cases, other sorting algorithms or the algorithm discussed in the next section would be more appropriate.

Implementation for this algorithm is similar to the one for sorting an array with 0s and 1s.

Optimal Solution (3 Pointer Approach)

Algorithm

Below is a single pass algorithm to sort all elements in the array containing only 0s, 1s and 2s:

1. Initialize three pointers:
   • low: Initially points to the start of the array
   • mid: Initially points to the start of the array
   • high: Initially points to the end of the array
2. Use mid pointer to iterate through the array:
   • If the element at mid is 0:
     • Swap it with the element at low
     • Move low and mid pointers one step right
   • If the element at mid is 1:
     • Leave it as is
     • Move mid pointer one step right
   • If the element at mid is 2:
     • Swap it with the element at mid
     • Move high pointer one step left
     • Don’t move mid pointer (we need to check the swapped element)
3. Repeat step 2 until mid pointer crosses high pointer
4. The array is now sorted with all 0s at the beginning, all 1s in the middle, and all 2s at the end.

The idea behind this algorithm is to use mid pointer to traverse the array and low pointer is used to indicate the position until which all the elements are 0s and high pointer is used to indicate the position from which all the elements are 2s until the end of array. Each time the mid pointer encounters 0, it moves it towards left and each time the mid pointer encounters 2, it moves it towards right.

This algorithm efficiently sorts an array containing only 0s, 1s, and 2s in a single pass, making it faster than traditional sorting methods for this specific scenario.

Step by Step Visualization

Below are the slides which visually walk you through the entire algorithm step by step:

Implementation

def dutch_national_flag(arr):
  # Initialize the three pointers
  low = 0
  mid = 0
  high = len(arr) - 1

  # Iterate through the array using the mid pointer
  while mid <= high:
    if arr[mid] == 0:
      # If the element at mid is 0,
      # swap it with the element at low
      arr[low], arr[mid] = arr[mid], arr[low]
      # Move both low and mid pointers to the right
      low += 1
      mid += 1
    elif arr[mid] == 1:
      # If the element at mid is 1,
      # leave it as is and move mid pointer
      mid += 1
    else:  # arr[mid] == 2
      # If the element at mid is 2,
      # swap it with the element at high
      arr[mid], arr[high] = arr[high], arr[mid]
      # Move high pointer to the left (backwards)
      high -= 1
      # Don't move mid pointer here as we need to check the swapped element

# Input array
input_array = [1, 0, 2, 1, 0, 1, 2, 2, 0, 1]
print("Input array:", input_array)
# Run the function which sorts the array in place
dutch_national_flag(input_array)
print("Sorted array:", input_array)

#include <stdio.h>
#include <stdlib.h>

void dutch_national_flag(int* arr, int size) {
  // Initialize the three pointers
  int low = 0;
  int mid = 0;
  int high = size - 1;

  // Iterate through the array using the mid pointer
  while (mid <= high) {
    if (arr[mid] == 0) {
      // If the element at mid is 0,
      // swap it with the element at low
      int temp = arr[low];
      arr[low] = arr[mid];
      arr[mid] = temp;
      // Move both low and mid pointers to the right
      low++;
      mid++;
    } else if (arr[mid] == 1) {
      // If the element at mid is 1,
      // leave it as is and move mid pointer
      mid++;
    } else {  // arr[mid] == 2
      // If the element at mid is 2,
      // swap it with the element at high
      int temp = arr[mid];
      arr[mid] = arr[high];
      arr[high] = temp;
      // Move high pointer to the left (backwards)
      high--;
      // Don't move mid pointer here as we need to check the swapped element
    }
  }
}

int main() {
  // Input array
  int input_array[] = {1, 0, 2, 1, 0, 1, 2, 2, 0, 1};
  int size = sizeof(input_array) / sizeof(input_array[0]);

  printf("Input array: ");
  for (int i = 0; i < size; i++) {
    printf("%d ", input_array[i]);
  }
  printf("\n");

  // Run the function which sorts the array in place
  dutch_national_flag(input_array, size);

  printf("Sorted array: ");
  for (int i = 0; i < size; i++) {
    printf("%d ", input_array[i]);
  }
  printf("\n");

  return 0;
}

#include <iostream>
#include <vector>

using namespace std;

void dutch_national_flag(vector<int>& arr) {
  // Initialize the three pointers
  int low = 0;
  int mid = 0;
  int high = arr.size() - 1;

  // Iterate through the array using the mid pointer
  while (mid <= high) {
    if (arr[mid] == 0) {
      // If the element at mid is 0,
      // swap it with the element at low
      swap(arr[low], arr[mid]);
      // Move both low and mid pointers to the right
      low++;
      mid++;
    } else if (arr[mid] == 1) {
      // If the element at mid is 1,
      // leave it as is and move mid pointer
      mid++;
    } else {  // arr[mid] == 2
      // If the element at mid is 2,
      // swap it with the element at high
      swap(arr[mid], arr[high]);
      // Move high pointer to the left (backwards)
      high--;
      // Don't move mid pointer here as we need to check the swapped element
    }
  }
}

int main() {
  // Input array
  vector<int> input_array = {1, 0, 2, 1, 0, 1, 2, 2, 0, 1};
  cout << "Input array: ";
  for (int num : input_array) {
    cout << num << " ";
  }
  cout << endl;

  // Run the function which sorts the array in place
  dutch_national_flag(input_array);

  cout << "Sorted array: ";
  for (int num : input_array) {
    cout << num << " ";
  }
  cout << endl;

  return 0;
}

function dutchNationalFlag(arr) {
  // Initialize the three pointers
  let low = 0;
  let mid = 0;
  let high = arr.length - 1;

  // Iterate through the array using the mid pointer
  while (mid <= high) {
    if (arr[mid] === 0) {
      // If the element at mid is 0,
      // swap it with the element at low
      [arr[low], arr[mid]] = [arr[mid], arr[low]];
      // Move both low and mid pointers to the right
      low++;
      mid++;
    } else if (arr[mid] === 1) {
      // If the element at mid is 1,
      // leave it as is and move mid pointer
      mid++;
    } else {  // arr[mid] === 2
      // If the element at mid is 2,
      // swap it with the element at high
      [arr[mid], arr[high]] = [arr[high], arr[mid]];
      // Move high pointer to the left (backwards)
      high--;
      // Don't move mid pointer here as we need to check the swapped element
    }
  }
}

// Input array
const inputArray = [1, 0, 2, 1, 0, 1, 2, 2, 0, 1];
console.log("Input array:", inputArray);
// Run the function which sorts the array in place
dutchNationalFlag(inputArray);
console.log("Sorted array:", inputArray);

import java.util.Arrays;

public class Main {
  public static void dutchNationalFlag(int[] arr) {
    // Initialize the three pointers
    int low = 0;
    int mid = 0;
    int high = arr.length - 1;

    // Iterate through the array using the mid pointer
    while (mid <= high) {
      if (arr[mid] == 0) {
        // If the element at mid is 0,
        // swap it with the element at low
        int temp = arr[low];
        arr[low] = arr[mid];
        arr[mid] = temp;
        // Move both low and mid pointers to the right
        low++;
        mid++;
      } else if (arr[mid] == 1) {
        // If the element at mid is 1,
        // leave it as is and move mid pointer
        mid++;
      } else {  // arr[mid] == 2
        // If the element at mid is 2,
        // swap it with the element at high
        int temp = arr[mid];
        arr[mid] = arr[high];
        arr[high] = temp;
        // Move high pointer to the left (backwards)
        high--;
        // Don't move mid pointer here as we need to check the swapped element
      }
    }
  }

  public static void main(String[] args) {
    // Input array
    int[] inputArray = {1, 0, 2, 1, 0, 1, 2, 2, 0, 1};
    System.out.println("Input array: " + Arrays.toString(inputArray));
    // Run the function which sorts the array in place
    dutchNationalFlag(inputArray);
    System.out.println("Sorted array: " + Arrays.toString(inputArray));
  }
}

Time and Space Complexity Analysis

Time Complexity: O(n) The algorithm performs a single pass through the array and examines each element exactly once and performs at most one swap operation per element. Since the number of operations is directly proportional to the input size, the time complexity is linear, O(n).

Space Complexity: O(1) This algorithm sorts the array in-place, meaning it doesn’t require any extra space that grows with the input size. It only uses a constant amount of extra space for the three pointers (low, mid, and high) and a few temporary variables for swapping. Therefore, the space complexity is constant, O(1).

Further Reading

Although the Dutch National Flag problem statement involves sorting an array with 3 distinct values, algorithms used to solve the problem can also be used for Three-way partitioning of an array with minor modifications. For example, consider the array shown below:

[4, 2, 7, 1, 5, 3, 6]

If we need to partition the array into 3 segments such that:

• First segment containing elements less than the pivot
• Second segment containing elements equal to the pivot
• Third segment containing elements greater than the pivot,

We can apply the 3 pointer approach to solve the problem of three way partitioning by thinking of all elements less than the pivot element as 0s, all elements equal to the pivot element as 1s and all elements greater than the pivot element as 2s. After applying this algorithm to our example array with 4 as the pivot element, we would end up with the below array:

[2, 1, 3, 4, 5, 7, 6]

In this result, all elements less than 4 are on the left, the pivot (4) is in the middle, and all elements greater than 4 are on the right. This is useful in various sorting and searching algorithms, such as quicksort with three-way partitioning.