アルゴリズムの分治-中項とk番目の小要素を探す

n個の並べ替えられた配列A[1…n]について、項目はその中間要素である.
nが奇数である場合、中項はシーケンスの(n+1)/2番目の要素である.
nが偶数である場合、n/2とn/2+1の位置にある2つの中間要素が存在し、この場合、n/2番目の最小要素を選択する.
このように,二つのケースを総合すると,中項は第
 
中項を探す直接的な方法は、すべての要素を並べ替えて中間の要素を取り出すことです.
しかし、n個の要素を有する集合において、中項または通常の意味でk番目の小要素は、最適な線形時間内に見つけることができ、この問題は選択問題とも呼ばれる.
その基本思想は以下の通りである:再帰アルゴリズムでは、各再帰呼び出しの区分ステップの後、要素の固定部分を捨て、残りの要素を再帰すると、問題の規模は幾何級数で減少し、すなわち、各呼び出し過程において、問題の規模は定数で減少する.
具体的には、どのようなオブジェクトを処理しても、アルゴリズムは1/3を破棄し、残りの2/3部分を再帰すると仮定すると、2回目の呼び出しでは要素の数が2 n/3、3回目の呼び出しでは4 n/9、4回目の呼び出しでは8 n/27などとなる.ここで、各呼び出しにおいて、アルゴリズムが各要素に消費する時間が定数を超えないと仮定すると、すべての要素を処理するすべての時間を費やしてジオメトリレベル数を生成する
   cn + (2/3)cn + (2/3)2cn + ... + (2/3)jcn + ...   < 3cn
これはちょうどアルゴリズムを選ぶ仕事です.以下に示すk番目の小要素を探すアルゴリズムSelectは同様の方法で動作する.
 
まず、要素の個数が予め定義されたバルブ値44より小さい場合(バルブ値は自分で決めることができ、ここではまず44と定義する)、アルゴリズムは直接的な方法を用いてk番目の小要素を計算する.
次に、n個の要素をn/5
各グループをソートし、その中項である3番目の要素を取り出します.次に、これらの中項シーケンスの中項要素をmmとし、再帰計算により得られる.
次に、元の配列を、mm以下、等しい、および大きい要素をそれぞれ含むA 1、A 2、およびA 3の3つの配列に分割する.
最後に、k番目の小さい要素が3つの配列のいずれに現れるかを求め、テスト結果に基づいてk番目の小さい要素を返すか、A 1またはA 3上で再帰する.
 
プロセスSelect
n個の要素の配列A[1…n]と整数kを入力し、1≦k≦n
出力Aのk番目の小要素
 
アルゴリズム記述select(A,low,high,k)
1. n ← high - low + 1
2.if n<44 then Aをreturnに並べ替える(A[k])
3.命令q=⌊n/5⌋.Aをqグループに分け、各グループに5要素ずつ分けます.5がnを完全に除去しない場合、残りの要素は除外されます.
4.qグループの各グループを個別に並べ替え、中項を探し出す.すべての中項の集合はMである.
5.mm←select(M,1,q,⌈q/2⌉){mmは中項集合の中項}
6.A[low…high]を三つのグループに分ける
    A1 = { a | a < mm }
    A2 = { a | a = mm }
    A3 = { a | a > mm }
7. case
    |A1| ≥ k : return select(A1, 1, |A1|, k)
    |A1| + |A2| ≥ k : return mm
    |A1| + |A2| < k : return select(A3, 1, |A3|, k - |A1| - |A2|)
8. end case
 
アルゴリズムの配列は数学的な角度で記述されており,開始インデックスはすべて1であり,プログラムで実現する際には注意が必要である.
ここではMergeSortでこのアルゴリズムに必要なソート操作を完了します.もちろん、他のソート方法も使用できます.

public static int select(int[] sourceArray, int low, int high, int nthMinIndex)
{
	if (nthMinIndex < 0 || low > high)
		return -1;

	int sourceLength = high - low + 1;
	if (nthMinIndex >= sourceLength)
		return -1;

	if (sourceLength < 44)
	{
		mergeSort(sourceArray, low, high);
		return sourceArray[nthMinIndex];
	}

	int middleArrayLength = 5;
	int middleArrayQuantity = sourceLength / middleArrayLength;

	int[] middleValueArray = new int[middleArrayLength];
	for (int i = 0; i < middleArrayLength; i++)
	{
		mergeSort(sourceArray,
			i * middleArrayQuantity, (i + 1) * middleArrayQuantity - 1);
		int middleIndex = ((i * 2 + 1) * middleArrayQuantity - 1) / 2 +
			(((i * 2 + 1) * middleArrayQuantity - 1) % 2 == 0 ? 0 : 1);
		middleValueArray[i] = sourceArray[middleIndex];
	}

	int middleValue = select(middleValueArray, 0, middleArrayLength - 1,
		(middleArrayLength - 1) / 2 + ((middleArrayLength - 1) % 2 == 0 ? 0 : 1));
	
	List<Integer> lessThanMiddleValueList = new LinkedList<Integer>();
	List<Integer> equalsWithMiddleValueList = new LinkedList<Integer>();
	List<Integer> greaterThanMiddleValueList = new LinkedList<Integer>();
	for (int i = 0; i < sourceArray.length; i++)
	{
		if (sourceArray[i] < middleValue)
		{
			lessThanMiddleValueList.add(sourceArray[i]);
		}
		else if (sourceArray[i] == middleValue)
		{
			equalsWithMiddleValueList.add(middleValue);
		}
		else
		{
			greaterThanMiddleValueList.add(sourceArray[i]);
		}
	}

	Integer[] lessThanMiddleValueArray = new Integer[lessThanMiddleValueList.size()];
	lessThanMiddleValueList.toArray(lessThanMiddleValueArray);

	Integer[] greaterThanMiddleValueArray =
		new Integer[greaterThanMiddleValueList.size()];
	greaterThanMiddleValueList.toArray(greaterThanMiddleValueArray);

	if (lessThanMiddleValueList.size() > nthMinIndex)
	{
		return select(ArrayUtils.toPrimitive(lessThanMiddleValueArray),
			0, lessThanMiddleValueList.size() - 1, nthMinIndex);
	}
	else if (lessThanMiddleValueList.size() + equalsWithMiddleValueList.size()
		> nthMinIndex)
	{
		return middleValue;
	}
	else
	{
		return select(ArrayUtils.toPrimitive(greaterThanMiddleValueArray),
			0,
			greaterThanMiddleValueList.size() - 1,
			nthMinIndex
				- lessThanMiddleValueList.size() - equalsWithMiddleValueList.size());
	}
}