C ++を使用して、0、1、および2の配列を並べ替えます

0、1、および2の配列が与えられた場合、すべてのゼロが1の前に最初に来て、すべての2が最後になるように、要素を並べ替えます。配列のすべての要素をインプレースで並べ替える必要があります。

この問題は、DNF（Dutch National Flag）ソートアルゴリズムを使用して解決できます。たとえば、

入力-1 −

arr[ ]= {2,0,0,1,2,1 }

出力 −

0 0 1 1 2 2

説明 − DNF並べ替えアルゴリズムを使用して0、1、2を含む要素の指定された配列を並べ替えると、出力が{0,0,1,1,2,2}として出力されます。

入力-2 −

arr[ ]= {0,1,1,2,1,1,0}

出力 −

0 0 1 1 1 1 2

説明 − DNF並べ替えアルゴリズムを使用して0、1、2を含む要素の指定された配列を並べ替えると、出力が{0,0,1,1,1,1,2}として出力されます。

この問題を解決するためのアプローチ

与えられた0、1、2の配列では、DNFソートアルゴリズムを使用できます。

DNFソートアルゴリズム −アルゴリズムでは、必要な要素を交換して配列全体を反復処理するために3つのポインターが必要です。

• 配列の先頭にローポインタを作成し、アレイの末尾にハイポインタを作成します。

• 配列の中点を見つけて、配列の最初から最後まで繰り返す中点も作成します。

• 配列の中間ポインタが「0」の場合は、低い方向を指す要素を交換します。ローポインタとミッドポインタをインクリメントします。

• 配列の中間ポインタが「2」の場合は、上位を指す要素と交換します。ミッドポインタをインクリメントし、ハイポインタをデクリメントします。

• 配列のミッドポインタが「1」の場合は、ミッドポインタを増やします。

例

#include<iostream>
using namespace std;
void dnfsort(int a[], int n){
   int low= 0;
   int high= n-1;
   int mid=0;
   while(mid<=high){
      if(a[mid]==0){
         swap(a[mid],a[low]);
         mid++;
         low++;
      }
      if(a[mid]==1){
         mid++;
      }
      if(a[mid]==2){
         swap(a[mid],a[high]);
         high--;
      }
   }
}
int main(){
   int a[]= {1,0,0,2,1,1,0,0,1};
   int n= sizeof(a)/sizeof(int);
   dnfsort(a,n);
   for(int i=0;i<n;i++){
      cout<<a[i]<<" ";
   }
   return 0;
}

出力

上記のコードを実行すると、次のように出力が生成されます

0 0 0 0 1 1 1 1 2