 ### 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 340 1
C++ program to Sort a Linked List Using Merge Sort 316 1
C++ Program to Implement a Linked List representation of a Binary tree 295 1
C++ Program to Check for balanced parentheses in an expression 199 1
C++ Program to Perform Inorder, Preorder, Postorder traversals in a binary tree. 247 1
C++ program to print Indian flag 290 1
C++ program to Convert a multi level linked list to a singly linked list 201 1
C++ program to print right view of a Binary tree using queue 213 1
C++ Program to implement Huffman Coding Compression Algorithm 1268 1
C++ Program to Create a Height Balanced Binary Tree 241 1
C++ program to implement Prims algorithm 412 1
C++ Program for BFS Traversal 256 1
C++ Progam to Evaluate a Prefix Expression 296 1
C++ Program to Implement Queue using Linked List 224 1
C++ implementation of Stack using Linked list 247 1
C++ program to find the intersection point of two linked lists 288 1
C++ program to count the inversions in the given array 251 1
C++ program to perform D.N.F sort 294 1
C++ program to print all possible subsets of a String 261 1
C++ program to count the number of ones in a binary representation of a number 283 1
C++ program to print all possible subsets of a set 294 1
C++ program to find the largest word in a String 264 1
C++ Program to print a matrix in Spiral order 308 1
C++ program to convert from Binary to Decimal, Octal to Decimal, Hexadecimal to Decimal 277 1
C limits library 312 1
Program to add two Binary numbers 296 1