アルゴリズムの初歩（Insertion Sort） #アルゴリズム

ごく基本的なアルゴリズム、Insertion Sortについてです。なんでも、人に教えるというのは記憶の定着率を９０％にまで高めてくれるそうです。ちなみに、ただ本を読むのでは１０％。今アルゴリズムを学んでいるので、これからなるべく復習としてQiitaの記事にしていこうと思います。

このアルゴリズムは、一つのランダムに並んでいる数列を昇順や降順にソートします。ソートするデータのサイズが小さい時に効率的です。

Input
ソートされていない配列A[4,6,2,5,3,1]

Output
昇順にソートされた配列A’[1,2,3,4,5,6]

Method
以下をソートが完成するまで繰り返す：一つの数をKeyとしてとり、それを左の数と比べてKeyの方が小さいなら左の数をKeyにする。比べられた数の配列の場所を右にずらす。

では、手順を追って見ていきましょう。

６をKeyとする。Key(6)＞４なので、何もしない。Keyを右となりの数、２にする。
Key(2)＜６なので左の数(6)をKeyの位置に持ってくる。[4,6,２,5,3,1]→[4,6,６,5,3,1]　左の数をさらに一つ左にずらす(4になる)。 Key(2)＜４なので[４,6,6,5,3,1]→[4,4,6,5,3,1]。
左となりにもう数がないので、4をKeyにしてKeyを次の数、５にして再開。
上記の手順を繰り返す。

言葉にすると簡単ですね。では、これからPseudocode(スードーコード、簡略化された可読性の高いコード)で見ていきましょう。

pseudocode.java

    for (j=2 to A.length; j++) {
        Key = A[j]    
        i = j - 1;    //Keyの一つ左の数
        while (Key < A[i] and i > 0) {
            A[i + 1] = A[i];    //左の数を右に移動　1st loop[4,6,６,5,3,1]→ 2nd loop[4,４,6,5,3,1]
            i = i - 1;    //さらに一つ左にずらす
        }//このwhileループが終わった時、数が重複していることに注意。[4,４,6,5,3,1]
        A[i + 1] = Key; //i=0で終了。配列の最初の場所に、Key=2を代入[2,4,6,5,3,1]して重複解消。
    }

と、このようになります。個人的には、A[i + 1] = A[i];の部分で配列の中に同じ数が存在するという点にすぐ気づかず、分かりづらかったです。
ちなみに、Insertion Sortは初めの配列がどの程度昇順に並んでいるかによって速度が変わってきます。何回もwhileループしたりしなかったりということですね。

降順もやって見ましょう

pseudocode.java

for (j=2 to A.length; j++) {
        Key = A[j]    
        i = j - 1;    //Keyの一つ左の数
        while (Key > A[i] and i > 0) {
            A[i + 1] = A[i];    //左の数を右に移動　1st loop[4,6,６,5,3,1]→ 2nd loop[4,４,6,5,3,1]
            i = i - 1;    //さらに一つ左にずらす
        }//このwhileループが終わった時、数が重複していることに注意。
        A[i + 1] = Key;
    }

Javaでの実装は簡単そうなのでこの辺で。理解しながらこの記事を書いたので修正点がいくつかありました。分かりづらいことがあったらコメントしていただけると幸いです。