ナットとボルトの問題をクイックソートで解く方法【C++実装例つき】

ナットとボルトの問題（Nut and Bolt Problem）は、アルゴリズム分野でよく知られるマッチング問題の一つです。異なるサイズのナットのリストとボルトのリストがそれぞれ与えられ、各ナットにぴったり合うボルトを見つけて対応付けることが目的です。通常、この問題には「ナット同士・ボルト同士は直接比較できない」という制約があり、比較はナットとボルトの間でのみ行えるものとされています。

この問題はクイックソートの考え方を応用すると効率的に解けます。まずボルトのリストの末尾の要素をピボットとして選び、それを基準にナットのリストを再配置することで、そのピボットに対応するナットの最終的な位置を確定します。続いて、確定したナットを今度はピボットとしてボルトのリストを同様に分割します。この処理を左右の部分リストに対して再帰的に繰り返すことで、すべてのナットとボルトの組み合わせを揃えられます。

入力と出力

入力：ナットのリストとボルトのリスト

nuts = { ),@,*,^,(,%,!,$,&,#}
bolts = { !, (, #, %, ), ^, &, *, $, @ }

出力：マッチング後のナットとボルトの並び（両リストとも同一の順序になります）

After matching nuts and bolts:
Nuts:  ! # $ % & ( ) * @ ^
Bolts: ! # $ % & ( ) * @ ^

アルゴリズム

partition(array, low, high, pivot)

入力：配列1つ、lowとhighのインデックス、ピボット要素

出力：ピボット要素の最終的な位置

Begin
    i := low
    for j in range low to high, do
       if array[j] < pivot, then
          swap array[i] and array[j]
          increase i by 1
       else if array[j] = pivot, then
          swap array[j] and array[high]
          decrease j by 1
    done

    swap array[i] and array[high]
    return i
End

この手続きは、ピボットより小さい要素を配列の左側へ集め、ピボットそのものを適切な位置へ移動させます。ピボットと等しい要素はいったん末尾に退避させることで、無駄な比較を防いでいます。

nutAndBoltMatch(nuts, bolts, low, high)

入力：ナットのリスト、ボルトのリスト、範囲の下限・上限インデックス

出力：対応するナットとボルトの組み合わせを確定し、表示する

Begin
    pivotLoc := partition(nuts, low, high, bolts[high])
    partition(bolts, low, high, nuts[pivotLoc])
    nutAndBoltMatch(nuts, bolts, low, pivotLoc-1)
    nutAndBoltMatch(nuts, bolts, pivotLoc + 1, high)
End

まずボルト側の末尾の要素をピボットにしてナットのリストを分割し、そこで確定した位置のナットを、今度はボルト側を分割するためのピボットとして利用します。これにより、両リストの同じインデックス位置に必ず一致するペアが揃う仕組みです。その後、ピボット位置より左側と右側の部分配列に対して、それぞれ再帰的に同じ処理を適用します。

C++による実装例

#include<iostream>
using namespace std;

void show(char array[], int n) {
    for(int i = 0; i<n; i++)
       cout << array[i] << " ";
}

int partition(char array[], int low, int high, char pivot) {     //クイックソート用にピボットの位置を求める
    int i = low;
    for(int j = low; j<high; j++) {
       if(array[j] <pivot) {     //j番目の要素がピボット未満なら、i番目の要素と交換
          swap(array[i], array[j]);
          i++;
       }else if(array[j] == pivot) {     //j番目の要素がピボットと等しければ、末尾の要素と交換
          swap(array[j], array[high]);
          j--;
       }
    }
    swap(array[i], array[high]);
    return i;     //ピボット要素の位置を返す
}

void nutAndBoltMatch(char nuts[], char bolts[], int low, int high) {
   if(low < high) {
      int pivotLoc = partition(nuts, low, high, bolts[high]);   //ボルト側の要素を選んでナットを分割
      partition(bolts, low, high, nuts[pivotLoc]);     //確定した位置関係をボルト側にも反映
      nutAndBoltMatch(nuts, bolts, low, pivotLoc - 1);
      nutAndBoltMatch(nuts, bolts, pivotLoc+1, high);
   }
}

int main() {
   char nuts[] = {')','@','*','^','(','%','!','$','&','#'};
   char bolts[] = {'!','(','#','%',')','^','&','*','$','@'};
   int n = 10;
   nutAndBoltMatch(nuts, bolts, 0, n-1);
   cout << "After matching nuts and bolts:"<< endl;
   cout << "Nuts:  "; show(nuts, n); cout << endl;
   cout << "Bolts: "; show(bolts, n); cout << endl;
}

出力結果

After matching nuts and bolts:
Nuts:  ! # $ % & ( ) * @ ^
Bolts: ! # $ % & ( ) * @ ^

計算量の目安

本手法の計算量はクイックソートと同様の振る舞いを示します。平均的には O(N log N) ですが、分割が毎回極端に偏る最悪ケースでは O(N²) まで悪化する可能性があります。一方で、追加の作業用配列をほとんど必要とせず、その場（in-place）で処理を完結できる点が大きな利点です。

まとめ

ナットとボルトの問題は、「ナット同士・ボルト同士を比較できない」という制約のもとで2つのリストを対応付ける古典的なアルゴリズム課題です。クイックソートのパーティション処理をナットとボルトに交互に適用するだけで、平均 O(N log N) で全てのペアをマッチングできる点がポイントです。分割統治の考え方がそのまま活きる好例といえるでしょう。