シェアソート

シェアソートは、ソートのアルゴリズムの一つ。シェアソートでは、データを長方形に並べた上で、各行／各列ごとにソートを行なう。1989年に Isaac D. Scherson らが発表した。安定ではない内部ソートであり、最悪の場合の時間計算量はOである。各行／各列の比較は互いに独立であるため、バブルソートとは異なり、並列動作が可能である。

1. アルゴリズム
---------

シェアソートの手順は、回の段階に分けられる。

奇数番目の段階
行ごとに、奇数行目は左側が小さく、偶数行目は右側が小さくなるようにソートする。
偶数番目の段階
列ごとに、上が小さくなるようにソートする。
最後の段階
行ごとに、左側が小さくなるようにソートする。

1.1. 実装例
--------

/

シェアソート サンプル
/public class ShearSort { /

画面表示用:一列いくつで表示するか
/private int col; /

ソートする配列
/private int array[];

/

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

/

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

/

配列の内容を表示する
@param msg 表示するメッセージ
/private void printArray { System.out.println; for { if  { System.out.println; } System.out.printf; } System.out.println; }

/

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

/

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

1.2. 動作例
--------

初期データ:

{| 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 |}

2. 関連項目
-------

奇偶転置ソート

3. 参照
-----

4. 外部リンク
--------

[1]