配列のソート方法のアルゴリズムについてまとめ。バブル選択挿入。

初めに

配列のソートアルゴリズムについて基本的な3つの方法を知ったので自分用にまとめる。
サンプルコードはjavaで書く。
バブルだけは全体のコード、他はソート部分だけを。

基本交換法(バブルソート)

bubble sort

public class TrySort{
    public static void main(String[] args) {
        // 適当な配列を作る
        int[] array = {3, 5, 4, 1, 2};

        // ++++++++++++++++++++++++++++++
        // バブルソート
        for(int i = array.length - 1; i > 0; i--){  // 内側ループ毎に終了回数を下げていく
            for(int j = 0; j < i; j++){ // 
                if(array[j] > array[j + 1]){  // 左側の方が大きければ入れ替える。
                    // 入れ替え
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
        // ++++++++++++++++++++++++++++++

        // 表示
        for(int i = 0; i < array.length; i++){
            System.out.printf("array[%d]...%d\n", i, array[i]);
        }
    }
}

あるインデックスjと隣接するインデックスj+1を比較、終わったら一つ右隣のインデックスをj(基準)にして繰り返す。(内側のループ)
これを配列の長さ-1周行う。減っていく(i--;)内側ループの最大値を外側のループで制御(j < i; 内側ループの最大値(比較の回数)を外側のループ毎のiの値に設定)。
一周するごとに最大値が順に確定するため比較の回数が少なくなっていく。
探索はn(n-1)/2回かかるらしい知らんけど

選択ソート

selection sort

        // 選択ソート
        for(int i = 0; i < array.length - 1; i++){
            for(int j = i + 1; j < array.length; j++){ // 外側ループのインデックスを基準としてその右~最後のインデックスまでをそれぞれ比較 
                if(array[i] > array[j]){  // 基準のほうが大きいなら入れ替える
                    // 入れ替え
                    int temp = array[j];
                    array[j] = array[i];
                    array[i] = temp;
                }
            }
        }

バブルソートの改良版。
あるインデックスにを基準として右のインデックス~最後のインデックスまでをそれぞれ比較
あるインデックスを外側のループで制御

挿入ソート

insertion sort

        // 挿入ソート
        for(int i = 0; i < array.length - 1; i++){  // [0]~[最後から一つ前]まで繰り返す
            for(int j = i; j >= 0; j--){ // 外側ループのインデックスを基準として、その右と比べ(※)入れ替え処理ができたなら、基準インデックスを左にずらし今入れ替えれた値を基準に変え、同じ処理を適した位置になるまで繰り返す(内ループ)。 
                if(array[j] > array[j + 1]){  // その右と比べ(※)ただしい順番に入れ替える
                    // 入れ替え
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }else{
                    break;  // それ以上左にずらせない適した位置まで移動出来たら内ループを抜ける
                }
            }
        }

あるインデックスと右のインデックスを比べ正しい位置になるまで左と交換し続ける
あるインデックスを外側のループで制御

おわり

ほかにもシェルソート、クイックソート、ヒープソートといったより高速なソートアルゴリズムもあるらしい。
今度まとめるかも。