DNF sorting ( 0s , 1s , 2s, sorting )

ABOUT  DNF SORTING

•  WHAT IS SORTING?

 

Sorting   is  a  process  of  arranging  items (  any things  ex :- ,elements in array  , table , marks , price of things etc)  in systematically  such that  in ascending  or descending   in form of  correctly  sequence .

1.        Ordering :- Arranging items  in a sequence ordered by some  strategy.

2.       Categorizing :- grouping elements in similar properties.

 

                               

WHAT IS DNF SORTING?

 

It is  also  known  as Dutch National Flag  .Some times   It is known   by   0 ,1, 2s sorting.   This sorting  is  implemented  only  three elements  i.e  we arrange the only  three  types of  element  elements    1 , 2 , 0 s   in  the array in the form of linear which  does nor  consume   more space  .

Explanation  of  DNF  SORT: -   In DNF sort generally array is distribute by four parts which consists   different colors  by different  LOW , Mid ,  HIGH pointers .

1.       First    parts   will consists  ZEREOS   and its   color  be  Red.

2.        Second   parts  consists  ONEs   one  its    color  be   White.

3.       Third    part  consists    unknown   which colors  be undetermine

4.       Fourth    part  consists  TWOs  which colors  be Blue

Ø Algorithm of   DNF  SORT .

v  Approch :

Ø  Approch

  Basically   , In  initial   time   all   elements  would  be   unknown   but  gradually  we   will   reduce     The unknown   region by step  by  step  and  other   elements  0, 1, 2 s  would  be  arranged  elements  in    zeroes  , ones , and twos    elements.

        Step 1 : -   Initially ,  keep  mid  pointer  at  starting   point   of array [].

        Step 2 :-    Check value of  array [ mid ]

       Step 3 :-    a ) After checking  ,  if  we will  get array [mid ]= 0;   then   do swapping  of   elements  array [ low]                             

            With array [ mid]     and  then  simply   increment   by  1 of mid  and low  such  that mid++,low++.

 

            b)  if   we  will  gwt   array [mid] =1   then  simply    do  increment by  1 to  mid such that  mid  ++

            

            c) if we  will   get   array[mid]  =2 then   so  swapping  of elements  of   array [ high ]  and  array [ mid] to

                  each   other   and   do  decrement by 1   of high such that   high--.                            

Ø WHAT IS DNF SORT?

 

It is  also  known  as Dutch National Flag  .Some times   It is known   by   0 ,1, 2s sorting.   This sorting  is  implemented  only  three elements  i.e  we arrange the only  three  types of  element  elements    1 , 2 , 0 s   in  the array in the form of linear which  does nor  consume   more space  .

Explanation  of  DNF  SORT: -   In DNF sort generally array is distribute by four parts which consists   different colors  by different  LOW , Mid ,  HIGH pointers .

1.       First    parts   will consists  ZEREOS   and its   color  be  Red.

2.        Second   parts  consists  ONEs   one  its    color  be   White.

3.       Third    part  consists    unknown   which colors  be undetermined

4.       Fourth    part  consists  TWOs  which colors  be Blue

Ø Algorithm of   DNF  SORT .

v  Approch :

Ø  Approach

  Basically   , In  initial   time   all   elements  would  be   unknown   but  gradually  we   will   reduce     The unknown   region by step  by  step  and  other   elements  0, 1, 2 s  would  be  arranged  elements  in    zeroes  , ones , and twos    elements.

        Step 1 : -   Initially ,  keep  mid  pointer  at  starting   point   of array [].

        Step 2 :-    Check value of  array [ mid ]

       Step 3 :-    a ) After checking  ,  if  we will  get array [mid ]= 0;   then   do swapping  of   elements  array [ low]                             

            With array [ mid]     and  then  simply   increment   by  1 of mid  and low  such  that mid++,low++.

 

            b)  if   we  will  gwt   array [mid] =1   then  simply    do  increment by  1 to  mid such that  mid  ++

            

            c) if we  will   get   array[mid]  =2 then   so  swapping  of elements  of   array [ high ]  and  array [ mid] to

                  each   other   and   do  decrement by 1   of high such that   high--.                            

 its  program is below :

• SEE FIGURE AND OBSERE FOR BETTER UNDERSTANDING

• IN BELOW FIGURE STEPWISE ALGORITHM  OCCURED.

click HERE and run this program

Input :   {  1, 1, 0, 2, 0, 1, 2, 0 }
Output: {  0, 0, 0 ,1, 1 ,1 ,2, 2}

#include <iostream>

using namespace std;

void swap (int arr[] ,int a,int b)
{ int x; x=arr[a];
arr[a]=arr[b]; arr[b]=x; }

void DSF ( int arr[],int n)

{int low=0, mid=0 , high=n-1;
for ( int i=0; mid<=high;i++ )
{ if(arr[mid]==0)
{ swap(arr ,low,mid);
low++; mid++; }

else if (arr[mid]==1)
{mid++;}

else if ( arr[mid]==2)
{swap(arr, mid,high);
high-- ;}

}

return ;
}

int main()

{ int n; n=8;

int arr[n]={1,1,0,2,0,1,2,0 } ;
DSF(arr,n);

for (int i=0; i<n;i++)
{cout<<arr[i]<<" ";}
return 0;

}

Ø     Complexity Analysis

·    Time Complexity :It is a amount of time taken by algorithm to run ,as a function of the length  of the input.

• Its Time  Complexity be  O(N)  because    we use the    in  build  sort function which has   o(n)  time   complexity.
•   Simple  we will see that

-     In each operation either mid be increment

-     Or high be decrement by 1 

 

• Space Complexity

 O(1) because we don’t use any auxiliary space here. 

     

• JOIN linkedln
• DOWNLOAD EBOOK  OF SORTING  MY TELEGRAM CHANNEL 
• (LINK  BELOW)
• CLICK HERE AND JOIN MY TELEGRAM CHANNEL FOR NEW UPDATES