Sorting, Simplified: A Beginner's Guide to the Dutch National Flag Algorithm.

Sorting, Simplified: A Beginner's Guide to the Dutch National Flag Algorithm.

ยท

4 min read

Given an array containing only 0s, 1s, and 2s. How do you sort it out?

you must be wondering, why is this even a question

isn't it inherent that we can just sort it, by maybe using some inbuilt function or maybe any of the sorting techniques?

Okay, so let me rephrase my question -

Given an array containing only 0s, 1s, and 2s. How do you sort it most optimally?

The Brute Force

Let's begin solving the problem using the brute-force approach, which is just sorting the array by a sorting technique.

since the most optimized sorting technique is merge sort, so we will be using that.

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

void merge(int arr[], int low, int mid, int high) {
    int left = low;
    int right = mid + 1;

    vector<int> temp;
    while(left <= mid && right <= high) {
        if (arr[left] < arr[right]) {
            temp.push_back(arr[left]);
            left++;    
        } else {
            temp.push_back(arr[right]);
            right++;
        }
    }

    while(left <= mid) {
        temp.push_back(arr[left]);
        left++;
    }

    while(right <= high) {
        temp.push_back(arr[right]);
        right++;
    }

    for (int i = low; i <= high; i++) {
        arr[i] = temp[i - low];
    }
}

void mergeSort(int arr[], int low, int high) {
    if (low >= high) return;
    int mid = (low + high) / 2;

    mergeSort(arr, low, mid);
    mergeSort(arr, mid + 1, high);
    merge(arr, low, mid, high);
}

int main() {
    int arr[] = {0,1,0,2,0,0,1,2,2,1,2,1,0};
    mergeSort(arr, 0, 13);

    for (int i = 0; i < 13; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

The time complexity for the brute force approach comes out to be O(NLogN).

The Better

It can be more optimized by observing the fact that we only have three types of numbers in the array, and if we can maintain the count of each of them then that can be used to overwrite the array.

#include<iostream>
using namespace std;

int main() {
    int arr[] = {0,1,0,2,0,0,1,2,2,1,2,1,0};
    int count0 = 0, count1 = 0, count2 = 0;

    // counting the count of 0s, 1s and 2s and storing in different 
    // variables
    for (int i = 0; i < 13; i++) {
        if (arr[i] == 0) count0++;
        else if (arr[i] == 1) count1++;
        else count2++;
    }

    // replacing the starting elements with 0s
    for (int i = 0; i < count0; i++) {
        arr[i] = 0;
    }

    // replacing the middle elements with 1s
    for (int i = count0; i < count1 + count0; i++) {
        arr[i] = 1;
    }

    // replacing the end elements with 2s
    for (int i = count1 + count0; i < 13; i++) {
        arr[i] = 2;
    }

    for (int i = 0; i < 13; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

The time complexity for the better approach comes out to be O(2N).

The Optimal

We can write the most optimized code by using Dutch National Flag Algorithm. Let's understand what it is -

Let's take three variables - low, mid, and high.

These variables will be diving the array into 4 parts -

  1. 0 .... low - 1: contains all 0s

  2. low .... mid - 1: contains all 1s

  3. mid ..... high: not sorted

  4. high + 1 ..... N - 1: contains all 2s

so in starting since the array is not sorted, so the first element of the array would be treated as mid and the last element as high.

Now what we have to do is to perform specific operations on a specific number that we encounter -

  1. 0: if we encounter 0, then we will swap it with low because 0 to low - 1 are 0s, and we have to, place all 0s together. By doing that, we will also increase the value of low and mid

  2. 1: if we encounter 1, we won't be doing anything because it is at its correct position, we will only increase the value if mid.

  3. 2: if we encounter 2, we will swap it with high, because high - 1 to N - 1 are 2s and we have to place all 2s together. By doing that, we will also decrease the value of high.

Code can be written as -

#include<iostream>
using namespace std;

int main() {
    int arr[] = {0,1,0,2,0,0,1,2,2,1,2,1,0};
    int low = 0, high = 12, mid = 0;

    while(mid <= high) {
        if (arr[mid] == 0) {
            swap(arr[mid], arr[low]);
            mid++;
            low++;
        } else if (arr[mid] == 1) {
            mid++;
        } else {
            swap(arr[mid], arr[high]);
            high--;
        }
    }

    return 0;
}

Now, this is the most optimal way of sorting the array it only takes, O(N) time.

Hope you had learned something from this.
Thanks for scrolling!!

Did you find this article valuable?

Support Adesh Khanna by becoming a sponsor. Any amount is appreciated!

ย