シェアソート

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

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

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

実装例 /** * シェアソート サンプル */ 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); // 配列の長さは正の数 if (arrLen < 1) { System.err.println("不正な引数: " + args); 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);

動作例 初期データ: {| 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

関連項目 奇偶転置ソート

参照

外部リンク Sorting Algorithm Demo