シェアソート

シェアソート（）は、ソートのアルゴリズムの一つ。シェアソートでは、データを長方形に並べた上で、各行／各列ごとにソートを行なう。1989年に Isaac D. Scherson らが発表した。安定ではない内部ソートであり、最悪の場合の時間計算量はO(n1.5)である。各行／各列の比較は互いに独立であるため、バブルソートとは異なり、並列動作が可能である。
アルゴリズム.
シェアソートの手順は、formula_1回の段階に分けられる。
実装例.
 * シェアソート サンプル
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);
動作例.
初期データ:
奇数行目は左が小さく、偶数行目は右が小さくなるようにソートする。
列ごとに上が小さくなるようにソートする。
奇数行目は左が小さく、偶数行目は右が小さくなるようにソートする。
列ごとに上が小さくなるようにソートする。
奇数行目は左が小さく、偶数行目は右が小さくなるようにソートする。
列ごとに上が小さくなるようにソートする。
最後に、行ごとに左が小さくなるようにソートするとソートが完了する。