シェアソート
シェアソート（英: shear-sort）は、ソートのアルゴリズムの一つ。シェアソートでは、データを長方形に並べた上で、各行／各列ごとにソートを行なう。1989年に Isaac D. Scherson らが発表した[1]。安定ではない内部ソートであり、最悪の場合の時間計算量は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[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);
}
}
}
動作例
編集初期データ:
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
奇数行目は左が小さく、偶数行目は右が小さくなるようにソートする。
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
列ごとに上が小さくなるようにソートする。
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
奇数行目は左が小さく、偶数行目は右が小さくなるようにソートする。
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
列ごとに上が小さくなるようにソートする。
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
奇数行目は左が小さく、偶数行目は右が小さくなるようにソートする。
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
列ごとに上が小さくなるようにソートする。
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
最後に、行ごとに左が小さくなるようにソートするとソートが完了する。
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
関連項目
編集参照
編集- ^ Isaac D. Scherson; Sandeep Sen (1989). “Parallel sorting in two-dimensional VLSI models of computation”. Computers, IEEE Transactions on 38 (2): 238-249. doi:10.1109/12.16500.
外部リンク
編集 | この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。 |