[FEATURE] Addition of dnf_sort in sorting folder

[akshatnema]

Detailed description

DNF Sort

The Dutch national flag (DNF) problem is one of the most popular programming problems proposed by Edsger Dijkstra. The flag of the Netherlands consists of three colors: white, red, and blue. The task is to randomly arrange white, red, and blue balls such that balls of the same color are placed together. Similarly, we design a problem statement consisting of an array of 0s,1s, and 2s. The aim is to sort the arrays in ascending/descending order.

Problem Statement:

Given an array A[] consisting of 0s, 1s, and 2s. The task is to write a function that sorts the given array. The functions should put all 0s first, then all 1s and all 2s in last.

Complexity Analysis:

- Time Complexity: O(n). 
  Only one traversal of the array is needed.
- Space Complexity: O(1). 
  No extra space is required.

Context

Approach

The main context of this problem is to use the three-pointer method, (without storing the count of 0s,1s, and 2s in any data structure). In the three-pointer method, we track of following pointers:

1. low - tracks the position of 0s in the array.
2. mid - tracks all the elements in the array.
3. high - tracks the position of 2s in the array.

This approach although not widely used, but still, take a part in Sorting Algortihms because this algorithm uses O (n) time complexity and O(1) Space Complexity, which is much better than other sorting Algos.

Possible implementation

No response

Additional information

No response

[akshatnema]

Please assign this issue to me.

[Panquesito7]

@akshatnema, thank you for opening an issue. Next time, please read our contributing guidelines:

Please avoid opening issues asking to be "assigned” to a particular algorithm. This merely creates unnecessary noise for maintainers. Instead, please submit your implementation in a pull request, and it will be evaluated by project maintainers.