野次馬エンジニア道

野次馬な気持ちでプログラミングをあれこれと綴ります

ソートと探索

前回は、計算量とグラフの走査についてまとめた。

手っ取り早くソート

簡単なプリミティブな配列で昇順であれば

int[] a = {4, 3, 2, 1};
java.util.Arrays.sort(a);

Integerを使って書くと

List<Integer> _list = Arrays.asList(4,3,2,1);
Collections.sort(_list); //昇順
Collections.sort(_list, Collections.reverseOrder()); //降順

実際にはオブジェクトがCollectionに入っていて、何らかのプロパティを基準に並べることが多い。

Collections.sort(otherList, new Comparator<MyData>() {
    @Override
    public int compare(MyData a, MyData b) {
        return a.val < b.val  ?  -1 :  1;
    }
});

ソートをした後は、上位何件取得のように部分リストを返すユースケースもあるかもしれない。

Collections.subList(_list, 10 );

ついでにCollectionは下記でシャッフル可能。

Random rnd = new Random();
Collections.shuffle(_list, rnd);

ソートの計算量

アルゴリズム バブルソート クイックソート マージソート
時間 O(N*N) O(NlogN)最悪O(N*N) O(NlogN)
空間 O(1) O(logN) O(N)

バブルソートは2回ループが回るのでO(N*N)。クイックソートは分割の基準となる値が中央値になる保証がないので最悪O(N*N)、再帰の実装のメモリでO(LogN)。

ソートそのものはライブラリに任せるとしても、小さい問題に分割してあとからマージする考え方は重要。分割統治法(divide and conquer)の代表的な例となる。

探索

前回に見た二分木の走査もノードを発見して打ち切るのであれば、一種の探索といえる。

二分探索

ここでは二分探索を見てみる。

int binarySearch( int a[], int val, int left, int right ) {
    if( left < right ) {
        int mid = ( left + right ) / 2;
        if( val > a[mid] ) {
            return binarySearch( a, val, mid + 1, right );
        } else if ( val == a[mid] ) {
            return mid:
        } else {
            return binarySearch( a, val, left, mid -1 );
        }
    }
}

線形に探索する場合O(N)なものがO(LogN)にできるのが最大のメリット。特に探索対象がブラックボックスで目的の値に辿りつきたい場合に非常に有効。