【ITニュース解説】Quick Select Algorithm

Quick Selectアルゴリズムは、与えられた配列の中から「K番目に小さい要素」を効率的に探し出すための手法である。すべての要素を完全にソートする必要がないため、非常に高速に目的の要素を見つけられる場合が多い。このアルゴリズムの核心は「パーティション分割（Partition Scheme）」という操作にある。パーティション分割とは、配列の中から基準となる「ピボット」という要素を一つ選び、そのピボットを正しい位置に配置すると同時に、ピボットより小さい要素をすべてピボットの左側に、ピボットより大きい要素をすべてピボットの右側に移動させる処理である。これにより、配列が二つの部分に分けられ、探しているK番目の要素がどちらの側に存在するのか、あるいはピボット自身がそのK番目の要素なのかを判断し、探索範囲を絞り込むことができる。

記事では、いくつかのパーティション分割手法のうち、「Lomuto（ロムート）パーティション分割」という具体的な方法が紹介されている。この手法では、まず配列の最も右端にある要素をピボットとして選択する。そして、配列の左端から右端に向かって要素を走査していく。このとき、「i」と「j」という二つのポインタが重要な役割を果たす。「i」ポインタは、現時点までに見つかった「ピボット以下の要素」が占める領域のすぐ隣、つまり次にピボット以下の要素を置くべき位置を指している。初期状態では、配列の左端に設定される。「j」ポインタは、配列を左から右へと順にスキャンしていく役割を持つ。

具体的には、j ポインタが配列の各要素を順番に見ていく。もし j が指す要素がピボット以下の値であった場合、その要素はピボットの左側に配置されるべきであるため、arr[i] と arr[j] の要素が入れ替えられる。そして、i ポインタは一つ右に移動し、次にピボット以下の要素を置く準備をする。もし j が指す要素がピボットより大きい値であった場合、その要素はピボットの右側に配置されるべきであるため、何もせずに j ポインタだけが次に進む。この処理を j ポインタがピボットの手前まで進む間、繰り返す。

ループが終了すると、i ポインタは「ピボット以下の要素」がすべて配置された領域のすぐ隣、すなわち「ピボットを配置すべき正しい位置」を指している。最後に、この arr[i] の要素と、最初にピボットとして選んだ arr[right] の要素を入れ替えることで、ピボットは正しい最終的な位置に置かれる。この時点で、i が指す位置より左側の要素はすべてピボット以下になり、i が指す位置より右側の要素はすべてピボットより大きくなる。こうして、配列は「ピボット以下の要素の集まり」「ピボット」「ピボットより大きい要素の集まり」の三つの部分に分割される。partition 関数はこのピボットの最終的な位置（インデックス）を返す。

例えば、配列 [10, 4, 5, 8, 6, 11, 26] の場合を考えてみよう。右端の 26 がピボットとして選ばれる。初期の i は 0 を指す。j が 0 から順に要素を走査する。arr[j] が 26 以下であれば arr[i] と交換し i を進める。この例ではすべての要素が 26 以下であるため、j が進むたびに arr[i] と arr[j] が交換され、i も一つずつ進む。j が 11 まで進むと、最終的に i は 6 を指すことになる。これは 26 が元々配列の最大値であったため、すべての要素が 26 以下という条件を満たし、i が配列の最後まで進んだ結果である。最後に arr[6] と arr[right]（つまり arr[6]）を交換するが、値は同じなので配列に変化はない。このパーティション分割は 6 というインデックスを返す。

このパーティション分割の仕組みを理解した上で、Quick Selectアルゴリズム本体である quickselect メソッドの動作を見ていく。このメソッドは再帰的に動作する。まず、探索範囲の左端 left と右端 right が同じになった場合、それは配列に要素が一つしかないことを意味するため、その要素がK番目の要素であると判断し、その値を返す。これが再帰の終了条件である。次に、self.partition(left, right) を呼び出して、現在の探索範囲の配列をパーティション分割し、ピボットの最終的なインデックス pivot_index を取得する。pivot_index がわかると、現在のピボットが、現在の部分配列において左から何番目の要素になるかを計算できる。これは pivot_index - left + 1 で求められる。この計算結果と、探している k 番目の要素が一致する場合、現在のピボットこそが探し求めていたK番目の要素であるため、arr[pivot_index] の値を返す。もし k が、ピボットの位置よりも小さい値（k < pivot_index - left + 1）であれば、K番目の要素はピボットの左側の部分配列の中に存在するとわかる。そのため、探索範囲を left から pivot_index - 1 までに絞り込み、quickselect(left, pivot_index - 1, k) を再帰的に呼び出す。反対に、もし k がピボットの位置よりも大きい値（k > pivot_index - left + 1）であれば、K番目の要素はピボットの右側の部分配列の中に存在するとわかる。このとき注意が必要なのは、右側の部分配列は元の配列の途中から始まるため、k の値も新しい部分配列の先頭を基準とした相対的な値に調整する必要があることだ。具体的には、k からピボットの位置までの要素数（pivot_index - left + 1）を引くことで、右側の部分配列におけるK番目の相対的な位置を計算する。そして、探索範囲を pivot_index + 1 から right までに絞り込み、quickselect(pivot_index + 1, right, k - (pivot_index - left + 1)) を再帰的に呼び出す。

このように、Quick Selectアルゴリズムはパーティション分割を繰り返し行うことで、一度の分割でK番目の要素が存在しない半分の範囲を捨て去り、効率的に探索範囲を縮小していく。これにより、ソートせずに目的の要素を見つけることが可能になる。これは、大量のデータから特定の順位の要素だけが必要な場合に、全体のソートよりもはるかに高速に処理を完了できるという大きな利点がある。システムエンジニアにとって、このようなアルゴリズムの知識は、プログラムの性能を向上させる上で非常に重要である。