シェアソートのソースを表示

'''シェアソート'''（{{lang-en-short|shear-sort}}）は、[[ソート]]の[[アルゴリズム]]の一つ。シェアソートでは、データを[[長方形]]に並べた上で、各行／各列ごとにソートを行なう。1989年に Isaac D. Scherson らが発表した<ref>{{cite journal
|title=Parallel sorting in two-dimensional VLSI models of computation
|author=Isaac D. Scherson
|author2=Sandeep Sen
|journal=Computers, IEEE Transactions on
|volume=38
|issue=2
|year=1989
|pages=238-249
|doi=10.1109/12.16500
|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.111.5839
}}</ref>。[[安定ソート|安定]]ではない内部ソートであり、最悪の場合の[[計算複雑性理論|時間計算量]]は[[ランダウの記号|O(n<sup>1.5</sup>)]]である。各行／各列の比較は互いに独立であるため、バブルソートとは異なり、並列動作が可能である。

== アルゴリズム ==
シェアソートの手順は、<math>2\left\lceil\left(\log_{2}\sqrt{n}\right)\right\rceil+1</math>回の段階に分けられる。

*奇数番目の段階(1,3,5,7･･･番目の段階)
**行ごとに、奇数行目は左側が小さく、偶数行目は右側が小さくなるようにソートする。
*偶数番目の段階(2,4,6,8･･･番目の段階)
**列ごとに、上が小さくなるようにソートする。
*最後の段階
**行ごとに、左側が小さくなるようにソートする。

===実装例===
<syntaxhighlight lang="java">
/**
 * シェアソート サンプル
 */
public class ShearSort {
    /**
     * 画面表示用:一列いくつで表示するか
     */
    private int col;
    /**
     * ソートする配列
     */
    private int array[];

    /**
     * 動作試験用メインルーチン
     */
    public static void main(String args[]) {
        // ソートしたい配列の長さ
        int arrLen;
        // 引数から配列の長さを取得
        if (args.length == 0) {
            // 省略時は100とする
            arrLen = 100;
        } else {
            arrLen = Integer.parseInt(args[0]);
            // 配列の長さは正の数
            if (arrLen < 1) {
                System.err.println("不正な引数: " + args[0]);
                System.exit(1);
            }
        }
        // 乱数を初期値として設定
        ShearSort obj = new ShearSort(arrLen);
        // 開始時刻の取得
        long stime = System.currentTimeMillis(); 
        // シェアソート実行
        obj.shearSort();
        // 終了時刻の取得
        long etime = System.currentTimeMillis(); 
        obj.printArray("ソート後 ");
        System.out.println("ShearSort: " + (etime - stime) + "ミリ秒");
    }

    /**
     * @param length 配列の要素数
     */
    private ShearSort(int length) {
        // 配列を確保
        array = new int[length];
        // 乱数を配列に設定
        for (int i = 0; i < length; i++) {
            array[i] = (int)(Math.random() * 1000);
        }
    }

    /**
     * 配列の内容を表示する
     * @param msg 表示するメッセージ
     */
    private void printArray(String msg) {
        System.out.println(msg);
        for(int i = 0; i < array.length; i++) {
            if (i % col == 0) {
                System.out.println();
            }
            System.out.printf(" %5d", array[i]);
        }
        System.out.println();
    }

    /**
     * 奇偶転置ソート
     * 配列の一部を行単位、列単位でソートする。
     * @param start ソート開始位置
     * @param end ソート終了位置
     * @param step ソート間隔
     * @param isinc ソート順序（true：昇順 false：降順）
     */
    private void oeTranSort(int start, int end, int step, boolean isinc) {
        boolean flag = false;
        do {
            flag = false;
            for (int i = start; i + step <= end; i += step * 2) {
                if ((isinc && (array[i] > array[i + step]))
                        || (!isinc && (array[i] < array[i + step]))) {
                    int temp = array[i];
                    array[i] = array[i + step];
                    array[i + step] = temp;
                    flag = true;
                }
            }
            for (int i = start + step; i + step <= end; i += step * 2) {
                if ((isinc && (array[i] > array[i + step]))
                        || (!isinc && (array[i] < array[i + step]))) {
                    int temp = array[i];
                    array[i] = array[i + step];
                    array[i + step] = temp;
                    flag = true;
                }
            }
        } while (flag);
    }

    /**
     * シェアソート
     * 配列をソートする。
     */
    private void shearSort() {
        // 配列の長さ
        final int len = array.length;
        // できるだけ大きく正方形に近い長方形ができるように並べる
        // 行数
        int row = (int)Math.sqrt(len);
        // 列数
        col = len / row;
        // 行数*列数で並べた時に余る個数
        int amari = len - row * col;
        if (amari != 0) {
            // 余りがあり行数が3以上の奇数の場合、余りが偶数行目に並ぶので
            // 一行減らして余りが奇数行目に並ぶように行数/列数を変更する
            if ((row % 2 == 1) && (row != 1)) {
                row--;
                col = len / row;
                amari = len - row * col;
            }
        }
        // 2を底とする行数の対数
        // ただし行数が2の累乗ちょうどの場合には、さらに+1する
        int exp = 1;
        // 2を底とする行数の対数
        int log = 0;
        while (exp <= row) {
            exp *= 2;
            log++;
        }
        // 配列の内容を表示
        printArray("ソート前 "); 
        // ソートする範囲の上限
        int max;
        for (int k = 0; k < log; k++) {
            // 行ごとに、奇数行目は左側が小さく、
            // 偶数行目は右側が小さくなるようにソートする
            for (int j = 0; j < row + (amari > 0 ? 1 : 0); j++) {
                // その行の末尾
                max = (j + 1) * col - 1;
                // あまった部分の行には、列数分のデータがない
                if (max >= len) {
                    max = len - 1;
                }
                // 当該行をソートする
                oeTranSort(j * col, max, 1, (j % 2) == 0);
            }
            // 列ごとに、上が小さくなるようにソートする。 
            for (int j = 0; j < col; j++) {
                // 余りのある列は、最初に求めた行数よりもデータが一つ多い
                oeTranSort(j, (row - (j < amari ? 0 : 1)) * col + j, 
                        col, true);
            }
        } // 規定回数分、行/列のソートを繰り返す
        // 行ごとに、左側が小さくなるようにソートする。 
        for (int j = 0; j < row + (amari > 0 ? 1 : 0); j++) {
            max = (j + 1) * col - 1;
            if (max >= len) {
                max = len - 1;
            }
            oeTranSort(j * col, max, 1, true);
        }
    }
}
</syntaxhighlight>

===動作例===
初期データ:
:{| rules="all" style="text-align:right"
| 25 ||  9 ||  5 || 19 || 20 ||  6 || 29
|-
|  8 || 24 || 32 || 14 || 34 || 10 || 28
|-
| 26 ||  3 || 18 ||  2 || 22 || 21 || 11
|-
| 17 || 27 || 15 || 23 || 13 || 35 || 30
|-
| 16 || 33 ||  4 || 31 ||  7 ||  1 || 12
|}

奇数行目は左が小さく、偶数行目は右が小さくなるようにソートする。
:{| rules="rows" style="text-align:right"
|  5 ||  6 ||  9 || 19 || 20 || 25 || 29
|-
| 34 || 32 || 28 || 24 || 14 || 10 ||  8
|-
|  2 ||  3 || 11 || 18 || 21 || 22 || 26
|-
| 35 || 30 || 27 || 23 || 17 || 15 || 13
|-
|  1 ||  4 ||  7 || 12 || 16 || 31 || 33
|}

列ごとに上が小さくなるようにソートする。
:{| rules="cols" style="text-align:right"
|  1 ||  3 ||  7 || 12 || 14 || 10 ||  8
|-
|  2 ||  4 ||  9 || 18 || 16 || 15 || 13
|-
|  5 ||  6 || 11 || 19 || 17 || 22 || 26
|-
| 34 || 30 || 27 || 23 || 20 || 25 || 29
|-
| 35 || 32 || 28 || 24 || 21 || 31 || 33
|}

奇数行目は左が小さく、偶数行目は右が小さくなるようにソートする。
:{| rules="rows" style="text-align:right"
|  1 ||  3 ||  7 ||  8 || 10 || 12 || 14
|-
| 18 || 16 || 15 || 13 ||  9 ||  4 ||  2
|-
|  5 ||  6 || 11 || 17 || 19 || 22 || 26
|-
| 34 || 30 || 29 || 27 || 25 || 23 || 20
|-
| 21 || 24 || 28 || 31 || 32 || 33 || 35
|}

列ごとに上が小さくなるようにソートする。
:{| rules="cols" style="text-align:right"
|  1 ||  3 ||  7 ||  8 ||  9 ||  4 ||  2
|-
|  5 ||  6 || 11 || 13 || 10 || 12 || 14
|-
| 18 || 16 || 15 || 17 || 19 || 22 || 20
|-
| 21 || 24 || 28 || 27 || 25 || 23 || 26
|-
| 34 || 30 || 29 || 31 || 32 || 33 || 35
|}

奇数行目は左が小さく、偶数行目は右が小さくなるようにソートする。
:{| rules="rows" style="text-align:right"
|  1 ||  2 ||  3 ||  4 ||  7 ||  8 ||  9
|-
| 14 || 13 || 12 || 11 || 10 ||  6 ||  5
|-
| 15 || 16 || 17 || 18 || 19 || 20 || 22
|-
| 28 || 27 || 26 || 25 || 24 || 23 || 21
|-
| 29 || 30 || 31 || 32 || 33 || 34 || 35
|}

列ごとに上が小さくなるようにソートする。
:{| rules="cols" style="text-align:right"
|  1 ||  2 ||  3 ||  4 ||  7 ||  6 ||  5
|-
| 14 || 13 || 12 || 11 || 10 ||  8 ||  9
|-
| 15 || 16 || 17 || 18 || 19 || 20 || 21
|-
| 28 || 27 || 26 || 25 || 24 || 23 || 22
|-
| 29 || 30 || 31 || 32 || 33 || 34 || 35
|}

最後に、行ごとに左が小さくなるようにソートするとソートが完了する。
:{| rules="rows" style="text-align:right"
|  1 ||  2 ||  3 ||  4 ||  5 ||  6 ||  7
|-
|  8 ||  9 || 10 || 11 || 12 || 13 || 14
|-
| 15 || 16 || 17 || 18 || 19 || 20 || 21
|-
| 22 || 23 || 24 || 25 || 26 || 27 || 28
|-
| 29 || 30 || 31 || 32 || 33 || 34 || 35
|}

== 関連項目 ==
* [[奇偶転置ソート]]

== 参照 ==
{{reflist}}

== 外部リンク ==
*[http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html Sorting Algorithm Demo]

{{ソート}}
{{Computer-stub}}

{{デフォルトソート:しえあそおと}}
[[Category:ソート]]