3-Wayクイックソート（オランダ国旗問題）とは？アルゴリズムとC++実装をわかりやすく解説

本記事では、クイックソートの改良版である「3-Wayクイックソート（スリーウェイクイックソート）」について詳しく解説します。基本的なクイックソートでは、まずピボット（基準値）となる要素を1つ選び、そのピボットを境に配列を分割します。その後、ピボットの左側と右側にある部分配列それぞれに対して、再帰的に同じ処理を繰り返すことで全体を整列させます。

一方、3-Wayクイックソートも同様の考え方に基づいていますが、配列を3つの領域に分割する点が大きな特徴です。配列 arr[1 to n] は以下のように分けられます。

• arr[1 to i]：ピボットより小さい要素の集まり
• arr[i + 1, j]：ピボットと等しい要素の集まり
• arr[j + 1, n]：ピボットより大きい要素の集まり

この分割手法は「オランダ国旗（Dutch National Flag）問題」としても知られており、特に同じ値が大量に含まれるデータを扱う場合に、通常のクイックソートよりも効率よく動作するという利点があります。

アルゴリズム

まず、partition（パーティション：分割）関数の擬似コードを見てみましょう。

begin
   if right – left <= 1, then
      if arr[right] < arr[left], then
         swap arr[right] and arr[left]
      i := left
      j := right
      return
   end if
   mid := left, pivot = arr[right]
   while mid <= right, do
      if arr[mid] < pivot, then
         swap arr[left], arr[mid]
         increase left and mid by 1
      else if arr[mid] = pivot, then increase mid by 1
      else
         swap arr[mid], arr[right]
         decrease right by 1
   done
   i := left – 1
   j := mid
end

次に、quicksort関数の擬似コードです。

begin
   if left >= right, then
      return
   end if
   define i and j
   partition(arr, left, right, i, j)
   quicksort(arr, left, i)
   quicksort(arr, j, right)
end

C++による実装例

それでは、上記のアルゴリズムをC++で実装したサンプルコードを紹介します。

#include<iostream>
#include<vector>
using namespace std;
// 配列を3つの領域に分割する関数
void partition(int arr[], int left, int right, int &i, int &j) {
   // 要素数が2個以下の場合
   if (right - left <= 1) {
      // 順序が逆なら交換
      if (arr[right] < arr[left])
         swap(arr[right], arr[left]);
      i = left;
      j = right;
      return;
}
int mid = left;
int pivot = arr[right];
while (mid <= right) {
   // ピボット未満 → 左端へ移動
   if (arr[mid]<pivot)
      swap(arr[left++], arr[mid++]);
      // ピボットと等価 → そのまま次へ
      else if (arr[mid]==pivot)
         mid++;
      // ピボット超過 → 右端へ移動
      else if (arr[mid] > pivot)
         swap(arr[mid], arr[right--]);
   }
   i = left-1;
   j = mid;
}
// 3-Wayクイックソート本体
void quicksort(int arr[], int left, int right) {
   if (left >= right) // 要素数が1または0の場合は終了
      return;
   int i, j;
   partition(arr, left, right, i, j);
   quicksort(arr, left, i);
   quicksort(arr, j, right);
}
// 配列の内容を表示する関数
void display(int arr[], int n) {
   for (int i = 0; i < n; ++i)
   cout << " " << arr[i];
   cout << endl;
}
int main() {
   int a[] = {4, 9, 4, 3, 1, 9, 4, 3, 9, 4, 3, 1, 4};
   int n = sizeof(a) / sizeof(int);
   display(a, n);
   quicksort(a, 0, n - 1);
   display(a, n);
}

出力結果

プログラムを実行すると、以下のように整列前後の配列が出力されます。

4 9 4 3 1 9 4 3 9 4 3 1 4
1 1 3 3 3 4 4 4 4 4 9 9 9

重複値（この例では「4」や「9」）が多い入力でも、3-Wayクイックソートは等しい要素を一括して中央の領域へまとめるため、無駄な比較・交換を減らし、効率よくソートできていることが確認できます。