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
- if(arr[mid] == 0)
Comments