 ### C++ program to perform D.N.F sort

Introduction:
DNF sort  also known as  Dutch National Flag.  We use the DNF sort algorithm to sort a vector of zeros, ones, and twos. It is very similar to what the counting sort does but, unlike the counting sort, it sorts the vector in place in a single iteration.
D.N.F algorithm:
• In this algorithm we  divide the array into three regions:
• 1. Region of 0s, this will start from the index 0 and continue till the last 0 of the vector.
• Region of 2s, it starts from the end index and continues till the last 2 is encountered.
• The middle region, region of 1s, it starts from the right boundary of region of 0s. And ends at the left boundary of region of 2s.
• 2.To traverse the vector we use three pointer approach.
• lo = 0: The right boundary of the middle region
• mid = 0: It represents the current iteration position
• high = N – 1: The right boundary of the middle region
• we mainly  to shrink the middle region to zero width.
•  3.So we run a while loop until mid becomes equal to high.
• while(mid <= high)
• To achieve this task, at each element we will perform some check and perform the swap if necessary.
•  4.So whenever we iterate over an element in the middle region, we peform the following steps.
• if(arr[mid] == 0)
• We will shift this element to the region of 0s by: swap(arr[mid++], arr[lo++])
• if(arr[mid] == 1)
• Do nothing, just move to the next element by: mid++
• otherwise, if(arr[mid] == 2)
• swap(arr[mid], arr[high–])
• Notice that in this case, we are not incrementing the mid pointer. This is because it is possible that mid might be pointing to a 0, and this might end up breaking the algorithm if we do not check this again.
• Program:
• #include<iostream>
• using namespace std;
• void swap(int arr[], int i, int j){
• int temp=arr[i];
• arr[i]=arr[j];
• arr[j]=temp;
• }
• void dnfSort(int arr[], int n) {
• int low=0;
• int mid=0;
• int high=n-1;
• while (mid<=high) {
• if(arr [mid]==0) {
•     swap(arr, low, mid);
• low++; mid++;
• }
• else if(arr [mid]==1) {
• mid++;

• }
• else{
• swap(arr,mid, high);
• high--;
• }
• }
• }
• int main(){
•     int k,i,arr;
•     cout<<"enter the number of elements you want to enter in the array "<<endl;
•     cin>>k;
•     cout<<"enter the elements in the array"<<endl;
•     cout<<"Note the elements must be either 0 or 1 or 2  ";
•     for(i=0;i<k;i++){
•         cin>>arr[i];
•     }
•     dnfSort(arr,k);
•     for(i=0;i<k;i++){
•         cout<<arr[i]<<" ";
•     }
•
• }
• Output:
• enter the number of elements you want to enter in the array
• 9
• enter the elements in the array
• Note the elements must be either 0 or 1 or 2  1 0 2 1 0 1 2 1 2
• 0 0 1 1 1 1 2 2 2 #### More Articles of Shaik Aftab Ahmed:

Name Views Likes
C++ Program to Find the Frequency of Odd & Even Numbers in the given Matrix 275 1
C++ program to Sort a Linked List Using Merge Sort 258 1
C++ Program to Implement a Linked List representation of a Binary tree 253 1
C++ Program to Check for balanced parentheses in an expression 166 1
C++ Program to Perform Inorder, Preorder, Postorder traversals in a binary tree. 213 1
C++ program to print Indian flag 248 1
C++ program to Convert a multi level linked list to a singly linked list 164 1
C++ program to print right view of a Binary tree using queue 183 1
C++ Program to implement Huffman Coding Compression Algorithm 544 1
C++ Program to Create a Height Balanced Binary Tree 186 1
C++ program to implement Prims algorithm 263 1
C++ Program for BFS Traversal 197 1
C++ Progam to Evaluate a Prefix Expression 181 1
C++ Program to Implement Queue using Linked List 191 1
C++ implementation of Stack using Linked list 201 1
C++ program to find the intersection point of two linked lists 243 1
C++ program to count the inversions in the given array 228 1
C++ program to perform D.N.F sort 259 1
C++ program to print all possible subsets of a String 233 1
C++ program to count the number of ones in a binary representation of a number 243 1
C++ program to print all possible subsets of a set 264 1
C++ program to find the largest word in a String 235 1
C++ Program to print a matrix in Spiral order 258 1
C++ program to convert from Binary to Decimal, Octal to Decimal, Hexadecimal to Decimal 249 1
C limits library 277 1
Program to add two Binary numbers 248 1