ソートアルゴリズム (14)

しつこくソートアルゴリズムを紹介します。今回はスムースソート (Smooth Sort) です。

このソートは以前に紹介したヒープソートを改良したものです。最悪計算時間はヒープソートと同様に O(nlogn) ですが、ソート対象が既に順番に並んでいるほど計算時間は少なくなり、完全にソート済みの場合の計算時間は O(n) となります。

このアルゴリズムにはレオナルド数という数列の特性が利用されています。

レオナルド数を求める関数 L(n) は、n が 0 または 1 であれば 1、そうでなければ L(n – 1) + L(n – 2) + 1 となるような値を返す関数です。

下の Java コードではメモ化 (memoization) というテクニックを使用して実装しています。

スムースソートは要素数がレオナルド数となるようにヒープを構築して、順番にならんでいる要素をなるべく移動しないようにしてソートします。

sort/SmoothSort.java

package sort;

import java.util.Arrays;
import java.util.Collections;

public class SmoothSort> {
    private static int[] leonardoMemo = { 1, 1 };

    public static int leonardo(int n) {
        if (n < leonardoMemo.length) { 
            if (leonardoMemo[n] != 0) { 
                return leonardoMemo[n]; 
            } 
        } else { 
            int newLength = leonardoMemo.length * 2; 
            leonardoMemo = Arrays.copyOf(leonardoMemo, 
                    (newLength > n) ? newLength : (n + 1));
        }
        return leonardoMemo[n] = leonardo(n - 1) 
                                        + leonardo(n - 2) + 1;
    }

    private static > void sift(E[] v, int head,
            int exp) {
        E t = v[head];
        while (exp > 1) {
            int r = head - 1;
            int l = head - 1 - leonardo(exp - 2);
            if (t.compareTo(v[l]) >= 0 &&
                                t.compareTo(v[r]) >= 0) {
                break;
            }
            if (v[l].compareTo(v[r]) >= 0) {
                v[head] = v[l];
                head = l;
                exp -= 1;
            } else {
                v[head] = v[r];
                head = r;
                exp -= 2;
            }
        }
        v[head] = t;
    }

    private static > void arrange(E[] v,
            int head, long frac, int exp) {
        E t = v[head];
        while (frac > 1) {
            int next = head - leonardo(exp);
            if (t.compareTo(v[next]) >= 0) {
                break;
            }
            if (exp > 1) {
                int r = head - 1;
                int l = head - 1 - leonardo(exp - 2);
                if (v[l].compareTo(v[next]) >= 0
                        || v[r].compareTo(v[next]) >= 0) {
                    break;
                }
            }
            v[head] = v[next];
            head = next;
            int trail = Long.numberOfTrailingZeros(frac - 1);
            frac >>>= trail;
            exp += trail;
        }
        v[head] = t;
        sift(v, head, exp);
    }

    public static > void sort(E[] v) {
        if (v.length == 0) return;
        int head = 0;
        long frac = 0;
        int exp = 0;
        while (head < v.length) { 
            if ((frac & 3) == 3) { 
                frac >>>= 2;
                exp += 2;
            } else if (exp > 1) {
                frac <<= exp - 1;
                exp = 1;
            } else {
                frac <<= exp; 
                exp ^= 1; 
            } 
            frac++; 
            if (exp > 0 && v.length - head - 1 <
                                           leonardo(exp - 1) + 1) { 
                arrange(v, head, frac, exp); 
            } 
            sift(v, head, exp); 
            head++; 
        } 
        arrange(v, head - 1, frac, exp); 
        while (head > 0) {
            head--;
            if (exp > 1) {
                frac <<= 2; 
                frac--; 
                exp -= 2; 
                arrange(v, head - leonardo(exp) - 1, frac >> 1, exp + 1);
                arrange(v, head - 1, frac, exp);
            } else {
                int trail = Long.numberOfTrailingZeros(frac - 1);
                frac >>= trail;
                exp += trail;
            }
        }
    }

    public static void main(String... args) {
        Integer[] v = new Integer[10];
        for (int i = 0; i < v.length; i++) {
            v[i] = i;
        }
        Collections.shuffle(Arrays.asList(v));
        System.out.println(Arrays.toString(v));
        sort(v);
        System.out.println(Arrays.toString(v));
    }
}

2010年3月24日 | カテゴリー：アルゴリズム