データ構造とアルゴリズム勉強会 #1

先日より大学の有志にて競技プログラミングで使用するアルゴリズムを学ぶ勉強会を始めました。ここでは学んだことの整理と発信のためにその日の内容を記事にします。競技プログラミング、特にAtCoder初心者の方の参考になれば幸いです。

勉強会の概要

名前の通り、『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』(通称:螺旋本)の内容を有志が発表、擬似コードを通してアルゴリズムの概念を理解し実装するという内容です。実装はAIZU ONLINE JUDGEの問題を使用しています。AtCoderに代表される競技プログラミングの地力をつけることが目的ですが、アルゴリズムを学ぶことでプログラミングそのものの地力も上がるのではないかと思い参加することにしました。

第1回目の内容

・計算量(省略)
・挿入ソート
・バブルソート
・選択ソート

挿入ソート(insertion sort)

問題:ALDS1_1_A

イメージとしてはランダムなトランプを小さい順に並び替えたい時、とりあえず１枚目から順に引っ張り出して適当な場所に挿し込むというような感じです。

ソート部分のコードは以下のようになります。

void insertion_sort(vector<int> &a){
    for (int i = 1; i < a.size(); ++i){
        auto v = a[i];
        auto j = i - 1;
        while (j >= 0 && a[j] > v) {
            a[j + 1] = a[j];
            j--;  
        }
        a[j + 1] = v;
    }
}

配列の引数に参照をつけていることに注意してください。余計なコピーが減ります。
このアルゴリズムの中身ですが、まずi番目の数字(ここでは5だとします。)をint vで参照しておきます。次にi-1番目、i-2番目、…と引っ張った数字より前の部分を確認していき、 5より大きい数字が出てきたらインデックスを１つずらします。そして最初に出会った５より小さい数字の後ろに5を挿入します。
例えば以下のようになります。

[1, 3, 6, 9, 8, 5]

[1, 3, 6, 9, 8,  ] <= 5を取り出す

[1, 3,  , 6, 9, 8] <= 5より大きい部分の要素のインデックスを1つずらす

[1, 3, 5, 6, 9, 8] <= 5を挿入

以上の作業をソートが完了するまで繰り返していきます。
while文の2つ目の条件に等号がないため、引っ張った数字と配列の数字が同じだった場合はその数字のあとに引っ張った数字が挿入され、同じ数字同士の順番が入れ替わることはありません。いわゆる安定的なソートです。
計算量は最悪の場合O(N^2)(数字が完全に逆順の場合)となり、あまり効率的なソートとは言えません。

バブルソート(bubble sort)

問題:ALDS1_2_A
次にバブルソートですが、これは大きい数字がボコボコと浮かび上がってくるイメージなのでそう呼ばれているそうです。

void bubble_sort(vector<int> &v){
    while (true) {
        bool swapped = false;
        for (int i = v.size() - 1; i >= 1; --i) {
            if (v[i] < v[i - 1]){
                swap(v[i], v[i - 1]); //要素の交換
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

こちらも配列を参照しています。
bool型のflagを立て、flagがtrueのうちは配列の前後の要素を交換していきます。
もし交換が成り立てばflagをtrueにし、次の交換が必要か判断します。
flagがwhile文の最初でfalseにされるため、if文の条件が成り立たなければ要素の交換もflagの論理値の変更もなされないため、その時点でソートは終了します。
交換は以下のようになります。

[1, 2, 4, 5, 3] <=ここでは3を交換していく

[1, 2, 4, 3, 5] <=3と5を比べ、5の方が大きいので2つの要素をスワップ

[1, 2, 3, 4, 5] <=3,4についても同様

[1, 2, 3, 4, 5] <=while文はもう一度回るが、条件文が成り立たないためここでソート終了。

計算量はO(N^2)で、安定なソートです。

#選択ソート(selection sort)
問題:ALDS1_2_B
選択ソートは最小の要素を選んで適切な位置に配置するアルゴリズムです。選択は要素そのものではなく、その要素のインデックスを用います。
コードは以下のようになります。

void selection_sort(vector<int> &a){
    for (int i = 0; i < a.size(); ++i){
        auto k = i;
        for (int j = i; j < a.size(); ++j) {
            if (a[j] < a[k]) k = j;
        }

        if(i != k) swap(a[i], a[k]);
    }
}

kという変数に配列のインデックスiを格納します。kは最小の値を持つ要素のインデックスjだと思っておけばこの後も理解しやすいです。
もしa[k]より後ろの要素でa[k]より小さい要素があれば、その要素のインデックスをkに格納していきます。これを繰り返すことでkには最小の要素のインデックスが格納されます。
kは最初はiですが、もしより後ろに最小の要素があればa[i]とa[k]を交換します。
具体的には下のようになります。

[1, 2, 4, 5, 3] <= 最初から調べていき、4を調べるループに入る。4のインデックスは[2]=i

[1, 2, 4, 5, 3] <= 5は4より大きいのでスルー。3は4より小さいので3のインデックス[4]をminjに格納。

[1, 2, 3, 5, 4] <= i != minjより、a[i]とa[minj]、つまり3と4を交換。

[1, 2, 3, 4, 5] <= 4と5でも同様の比較をしてソート終了。

これも計算量O(N^2)ですが、例えば[1, 2, 5, 5, 3]の場合1つめの5と最後の3が交換され、同じ数のインデックスが逆転してしまうため不安定なソートです。

#まとめ
今回は基本的なソートの実装を学びました。
挿入ソートは要素を選び適切な位置に挿し込む、バブルソートは前後の要素を大小比較して昇順に並び替えていく、選択ソートは最小値を選び、最初に当たった要素と入れ替えていく、といった具合です。
こうした方が伝わりやすいなどあれば適宜コメントをいただけると幸いです。