6

DNF Sort Using C++ [Easy Guide]

 2 years ago
source link: https://www.journaldev.com/59092/dnf-sort-using-cpp
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

In today’s article, we will implement DNF sort using C++. Just like other sorting algorithms, DNF sort is also a popular interview question. DNF sort is slightly different than the counting sort DNF sort is more time optimized as compared to the counting sort. Let’s see what does DNF sort means.

Also read: Bucket sort in C++

What Is DNF Sort?

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. We will also discuss the time and space complexity of this algorithm later in the article. The following example will help you get an intuition about the algorithm and its outcome.

Example

DNF Sort Concept

This is an in-place algorithm, i.e. it does not require any additional space for computation. The idea here is to swap at necessary positions while iterating through the array. The swap operations will sort some specific portion of the vector. Below are the steps that we will follow while writing the code.

  • Let’s divide the array into three regions
    • 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.
  • 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
  • Our objective is to shrink the middle region to zero width.
  • 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.
  • 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.

Implementing DNF Sort Using C++

Below is a C++ program that demonstrates the DNF sort algorithm as we’ve outlined the steps above.

#include <iostream>
#include <vector>
using namespace std;
// function to perform DNF Sort
void DNF_Sort(vector <int> &arr)
{
// initialize the pointers
int low = 0;
int mid = 0;
int high = arr.size() - 1;
// start the while loop and
// start shrinking the middle portion
while(mid <= high)
{
// for each element
// we will follow the
// logic given below
if(arr[mid] == 0)
{
// swap the elements
// and update the pointers
swap(arr[mid], arr[low]);
mid++;
low++;
}
else if(arr[mid] == 1)
{
// do nothing
mid++;
}
else if(arr[mid] == 2)
{
// swap the elements and
// update the pointers
// notice that we do not
// increment mid here
swap(arr[mid], arr[high]);
high--;
}
}
}
void print_vector(vector <int> v)
{
for(int ele : v)
cout << ele << " ";
cout << endl;
}
int main()
{
// Take the input
vector <int> arr;
cout << "Enter the elements, press -1 to stop" << endl;
while(true)
{
int ele;
cin >> ele;
if(ele == -1)
break;
arr.push_back(ele);
}
// call the DNF_Sort function
DNF_Sort(arr);
cout << "The sorted vector is:" << endl;
print_vector(arr);
}
Algorithm 1Algorithm 1

Output

DNF Sort OutputDNF Sort Output

Conclusion

In this article, we learned the DNF sorting algorithm used for sorting vectors of zeros, ones, and twos. First, we looked at the problem statement, then we moved to the concept. In the end, we coded the program to demonstrate a few examples. That’s all for now, thanks for reading.

Further Readings

To learn more about sorting algorithms, you can refer to the following websites.

https://www.journaldev.com/56329/merge-sort-in-cpp

https://www.journaldev.com/58641/wave-sort-using-cpp


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK