DNF Sort Using C++

By Ravi Kumar Mehta

Given an array of 0s, 1s and 2s. The idea is to write a function that sorts the given array by putting all 0s first then 1s and after that 2s. This code is written in c++.

Algorithm:

1. Initially keep the pointer low(lo)=0, high(hi)=n-1, mid=0.

2. Traverse the array from start to end and mid is less than or equal to high.

3. If the element of a[mid] is equal to 0 then swap the element of a[mid] with a[lo] and increment in low and mid.

4. If the element of a[mid] is equal to 1 then increment in mid.

5. If the element of a[mid] is equal to 2 then swap the element of a[mid] with a[hi] and decrement in high.

6. Print the sorted array.

 

input:- { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};

output:- 0 0 0 0 0 1 1 1 1 1 2 2