DNF Sort Using C++ [Easy Guide]

Filed Under: C++
DNF Sort Using C

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 1
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 1
Algorithm 1

Output

DNF Sort Output
DNF 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

close
Generic selectors
Exact matches only
Search in title
Search in content