DUTCH NATIONAL FLAG (DNF)

Sort an array of 0’s, 1’s, and 2’s

  • Brute force is to sort the array O(NlogN) we can do a lot better than that
  • Efficient approach is to just count the no of 1’s, 2’s and 3’s in one for loop and then put the values in the array in another loop O(N) time but it requires 2 traversals
  • Can we do this in just 1 traversal ? Yes !! DUTCH NATIONAL FLAG !!

ALGORITHM -

  • Take three-pointers, namely — low, mid, high.
  • We use low and mid pointers at the start, and the high pointer will point at the end of the given array.
  • low is for 0’s, mid is for 1’s and high is for 2’s (you would have figured this out already…I hope so xD)
  1. Index 0 to low - this is the "bottom group" (O’s)
  2. Index low to mid - this is the "middle group" (1’s)
  3. Index mid to high - this is the "top group" (2’s)

CASES :

  • If array [mid] =0, then swap array [mid] with array [low] and increment both pointers once.
  • If array [mid] = 1, then no swapping is required. Increment mid pointer once.
  • If array [mid] = 2, then we swap array [mid] with array [high] and decrement the high pointer once.

Time to get our hands dirty !!

int n = arr.size();
int low = 0, mid =0,high = n - 1;
while (mid <= hi) {
switch (a[mid]) {

// If the element is 0
case 0:
swap(a[low++], a[mid++]);
break;

// If the element is 1 .
case 1:
mid++;
break;

// If the element is 2
case 2:
swap(a[mid], a[high--]);
break;
}
}
}
low = 0  
high = arr_size - 1
mid = 0
while mid <= high:
if arr[mid] == 0:
arr[low],arr[mid] = arr[mid],arr[low]
low = low + 1
mid = mid + 1
elif arr[mid] == 1:
mid = mid + 1
else:
arr[mid],arr[high] = arr[high],arr[mid]
high = high - 1
return arr

Three way partitioning of an array around a given range

Input: arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32}  
lowVal = 14, highVal = 20
Output: arr[] = {1, 5, 4, 2, 1, 3, 14, 20, 20, 98, 87, 32, 54}

Your thought process

Nahhh !!
vector<int> threeWayPartition(vector<int> &arr, int a, int b)
{
int n = arr.size();
int low = 0, high = n - 1;
int index = 0;
// Traverse all elements of array
while (index <= high)
{
// Place elements less than a to front
if (arr[index] < a)
{
swap(arr[index], arr[low]);
index++;
low++;
}
// Place elements greater than b to back
else if (arr[index] > b)
{
swap(arr[index], arr[high]);
high--;
}
else
index++;
}
return arr;
}
Go code all that you learned today xD

Thank You !

--

--

--

A full stack developer and a curious person

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Compensating Transaction in Microservices

Day 23/ Start Next Project : Final walkthrough

Limits and supported functionality of SharePoint–Project sync

Hiring: Survival Guide in the Digital Future

Migrating an Existing WordPress Blog to Alibaba Cloud

The difference between OS and sys two modules in Python

Software For Creating Native Text Files On A Mac

Hello Everyone

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Vidhu Verma

Vidhu Verma

A full stack developer and a curious person

More from Medium

Communication between two separate GUIs via Multi-Threading

Pair Programming — Friend or Foe

Introduction to LTI 1.3

Need for different sorting algorithms