Sorting, Simplified: A Beginner's Guide to the Dutch National Flag Algorithm.
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 -
0 .... low - 1
: contains all 0slow .... mid - 1
: contains all 1smid ..... high
: not sortedhigh + 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 -
0: if we encounter 0, then we will swap it with
low
because 0 tolow - 1
are 0s, and we have to, place all 0s together. By doing that, we will also increase the value oflow
andmid
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
.2: if we encounter 2, we will swap it with
high
, becausehigh - 1
toN - 1
are 2s and we have to place all 2s together. By doing that, we will also decrease the value ofhigh
.
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!!