C++で0・1・2のみの配列をソートする方法｜DNF（オランダ国旗）アルゴリズムを解説

0、1、2 のみで構成された配列が与えられたとき、すべての「0」を先頭に、「1」をその次に、「2」を末尾に配置するように要素を並べ替えることを考えます。このとき、追加のメモリを使用せずに配列をインプレース（in-place）でソートする必要があります。

この問題は、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, 0, 1, 1, 1, 1, 2} の順に並べ替えられます。

この問題のアプローチ

0・1・2 のみからなる配列に対しては、DNFソートアルゴリズムを適用します。

DNFソートアルゴリズムとは： 3つのポインタを使いながら配列を走査し、必要な要素どうしを交換していくアルゴリズムです。手順は以下の通りです。

• 配列の先頭に low ポインタ、末尾に high ポインタを配置します。

• 配列の中間位置を基準に mid ポインタを作成し、配列の先頭から末尾まで走査させます。

• mid ポインタが指す要素が「0」の場合：low ポインタが指す要素と交換し、low と mid を両方とも1つ進めます。

• mid ポインタが指す要素が「2」の場合：high ポインタが指す要素と交換し、high を1つ戻します。

• mid ポインタが指す要素が「1」の場合：その場に正しい要素があるため、mid だけを1つ進めます。

この処理を mid ポインタが high ポインタを追い越すまで繰り返すことで、O(n) の計算量・定数メモリで配列をソートできます。

C++による実装例

#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

このように、DNFソートアルゴリズムを利用すれば、0・1・2 のみで構成された配列をたった1回の走査でインプレースに並べ替えることができます。