配列の並べ替えは不要で非効率的です。O(n) の平均実行時間を持つQuickSort ( QuickSelect ) アルゴリズムのバリエーションがあります。最初にソートすると、O(n log n) になります。実際には、リスト内で n 番目に小さい項目を見つけます。中央値の場合、n = リストの長さの半分を使用します。これを quickNth (list, n) としましょう。
概念は、n 番目に小さいものを見つけるために、「ピボット」値を選択することです。(正確にどのように選択するかは重要ではありません。データが完全にランダムであることがわかっている場合は、リストの最初の項目を取得できます。)
元のリストを 3 つの小さなリストに分割します。
- ピボットより小さい値を持つもの。
- ピボットと等しい値を持つもの。
- そして、ピボットより大きい値を持つもの。
次に、3 つのケースがあります。
- 「小さい」リストには >= n 個の項目があります。その場合、n 番目に小さいものがそのリストにあることがわかります。quickNth(より小さい, n) を返します。
- 小さい方のリストには < n 個の項目がありますが、小さいリストと等しいリストの長さの合計は >= n 個の項目があります。この場合、n 番目は「等しい」リスト内の任意の項目と等しくなります。あなたは終わった。
- n は、小さいリストと等しいリストの長さの合計よりも大きくなります。その場合、基本的にこれら 2 つをスキップして、それに応じて n を調整できます。quickNth(より大きい、n - 長さ (小さい) - 長さ (等しい)) を返します。
終わり。
データが完全にランダムかどうかわからない場合は、ピボットの選択についてより洗練する必要があります。リストの最初の値、リストの最後の値、および 2 つの値の中間にある値の中央値を取得すると、かなりうまく機能します。
ピボットの選択に運が悪く、ピボットとして常に最小値または最大値を選択すると、O(n^2) 時間かかります。良くないね。ただし、まともなアルゴリズムでピボットを選択した場合、それはほとんどありません。
サンプルコード:
import java.util.*;
public class Utility {
/****************
* @param coll an ArrayList of Comparable objects
* @return the median of coll
*****************/
public static <T extends Number> double median(ArrayList<T> coll, Comparator<T> comp) {
double result;
int n = coll.size()/2;
if (coll.size() % 2 == 0) // even number of items; find the middle two and average them
result = (nth(coll, n-1, comp).doubleValue() + nth(coll, n, comp).doubleValue()) / 2.0;
else // odd number of items; return the one in the middle
result = nth(coll, n, comp).doubleValue();
return result;
} // median(coll)
/*****************
* @param coll a collection of Comparable objects
* @param n the position of the desired object, using the ordering defined on the list elements
* @return the nth smallest object
*******************/
public static <T> T nth(ArrayList<T> coll, int n, Comparator<T> comp) {
T result, pivot;
ArrayList<T> underPivot = new ArrayList<>(), overPivot = new ArrayList<>(), equalPivot = new ArrayList<>();
// choosing a pivot is a whole topic in itself.
// this implementation uses the simple strategy of grabbing something from the middle of the ArrayList.
pivot = coll.get(n/2);
// split coll into 3 lists based on comparison with the pivot
for (T obj : coll) {
int order = comp.compare(obj, pivot);
if (order < 0) // obj < pivot
underPivot.add(obj);
else if (order > 0) // obj > pivot
overPivot.add(obj);
else // obj = pivot
equalPivot.add(obj);
} // for each obj in coll
// recurse on the appropriate list
if (n < underPivot.size())
result = nth(underPivot, n, comp);
else if (n < underPivot.size() + equalPivot.size()) // equal to pivot; just return it
result = pivot;
else // everything in underPivot and equalPivot is too small. Adjust n accordingly in the recursion.
result = nth(overPivot, n - underPivot.size() - equalPivot.size(), comp);
return result;
} // nth(coll, n)
public static void main (String[] args) {
Comparator<Integer> comp = Comparator.naturalOrder();
Random rnd = new Random();
for (int size = 1; size <= 10; size++) {
ArrayList<Integer> coll = new ArrayList<>(size);
for (int i = 0; i < size; i++)
coll.add(rnd.nextInt(100));
System.out.println("Median of " + coll.toString() + " is " + median(coll, comp));
} // for a range of possible input sizes
} // main(args)
} // Utility