奇数と偶数に分けてからソートを行うアルゴリズム

奇遇転置ソートを見ているときに、突然頭から湧きました。
その時の状況:
「奇数番同士の値と偶数番同士の値を比較して、ソートを行っているんだ～」
　　↓
「奇数と偶数だけでソートできそうだな～。あっできそうだから作ってみよ！」
こんな感じで作っていました。

仕組み

1. ソート対象データから、処理スタックに格納する
2. 処理スタックから、奇数グループと偶数グループに分ける
   • 奇数なら奇数グループ、偶数なら偶数グループに格納する
3. 奇数グループと偶数グループからデータを比較し、以下のように統合する
   • 昇順なら最小値を選択する
   • 降順なら最大値を選択する
4. 奇数グループと偶数グループから全て取り出すまで3.を繰り返す

今回は処理スタックとグループを配列で格納し、統合する前に前処理としてソートを行ってから統合していきます。

開発環境

• Java(OpenJDK 15.0.2)

ソースコード

OddEventMergeSort.java

public class OddEvenMergeSort {
    public static void sort(int[] inputs) {
        int stackPoint = inputs.length - 1;
        int getData = 0;

        int[] oddData = new int[inputs.length];
        int oddIndex = 0;
        int oddEndIndex = 0;
        int[] evenData = new int[inputs.length];
        int evenEndIndex = 0;
        int evenIndex = 0;

        for (; stackPoint >= 0; stackPoint--)
            if (inputs[stackPoint] % 2 == 1) {
                oddData[oddIndex] = inputs[stackPoint];
                oddIndex++;
            } else {
                evenData[evenIndex] = inputs[stackPoint];
                evenIndex++;
            }

        oddEndIndex = oddIndex - 1;
        evenEndIndex = evenIndex - 1;

        preSort(oddData,oddEndIndex);
        preSort(evenData,evenEndIndex);

        oddEndIndex++;
        evenEndIndex++;
        oddData[oddEndIndex] = Integer.MAX_VALUE;
        evenData[evenEndIndex] = Integer.MAX_VALUE;

        stackPoint = 0;
        oddIndex = 0;
        evenIndex = 0;

        while (oddIndex <= oddEndIndex - 1 || evenIndex <= evenEndIndex - 1) {
            getData = Math.min(oddData[oddIndex], evenData[evenIndex]);
            inputs[stackPoint] = getData;
            stackPoint++;
            if (getData % 2 == 1)
                oddIndex++;
            else
                evenIndex++;
        }

    }

    /*
     * 奇数、偶数に分けたデータをソートする
     */
    private static void preSort(int[] datas, int endIndex) {
        for (int i = 0, temp = 0; i <= endIndex; i++) {
            for (int j = 0; j <= endIndex - 1; j++) {
                if (datas[j + 1] <= datas[j]) {
                    temp = datas[j];
                    datas[j] = datas[j + 1];
                    datas[j + 1] = temp;
                }
            }
        }
    }
}

動作確認及び時間計測

ソートが終わるまでの時間を調べるため、詳細に調べるためナノ秒で計測しました。

Main.java

public class Main {
    public static void main(String[] args){
        int[] datas = {9,5,2,3,1};
        // 計測開始
        long startTime = System.nanoTime();
        OddEvenMergeSort.sort(datas);
        long endTime = System.nanoTime();
        // 計測終了

        for(int i=0;i < datas.length;i++){
            System.out.println(i + ":" + datas[i]);
        }
        System.out.println(endTime-startTime);
    }
}

結果

0:1
1:2
2:3
3:5
4:8
843500

0.8435mミリ秒となりました。
しかし、遅いのかどうか分からないためバブルソートと比較していきます。

バブルソートの場合

Main.java

public class Main {
    public static void main(String[] args){
        int[] datas = {8,5,2,3,1};
        // 計測開始
        long startTime = System.nanoTime();
        for (int i = 0, temp = 0; i <= datas.length; i++) {
            for (int j = 0; j <= datas.length - 2; j++) {
                if (datas[j + 1] <= datas[j]) {
                    temp = datas[j];
                    datas[j] = datas[j + 1];
                    datas[j + 1] = temp;
                }
            }
        }
        long endTime = System.nanoTime();
        // 計測終了
        for(int i=0;i < datas.length;i++){
            System.out.println(i + ":" + datas[i]);
        }
        System.out.println(endTime-startTime);
    }
}

出力結果

0:1
1:2
2:3
3:5
4:8
1900

1900ナノ秒
ミリ秒に直すと、0.0019ミリ秒になりました。

まとめ

バブルソートはすごい。
簡単なコードなのに、圧倒的に速く終わるバブルソートの時間に驚きました。
圧倒的に遅いですが、速度よりもロマン重視で作っていましたので最初に計測したときは「まあ遅いだろうね」というのが本音でした（笑）