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














































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[100];
      •     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

Comments