【Python基礎講座7】基本情報技術者試験対策 / 選択ソート(Selection Sort) / ソートアルゴリズムの解説

選択ソートとは

選択ソートはソートアルゴリズムの1つです。
(ソートアルゴリズムについては第5回の「ソートアルゴリズムとは」で説明しています。)

選択ソートでは以下を繰り返してデータを並べ替えます。

・昇順(小さい順)に並べる場合

  1. 未整列のデータの中から一番小さい要素を選択する
  2. 選択した要素と未整列のデータの先頭と入れ替える

・降順(大きい順)に並べる場合

  1. 未整列のデータの中から一番大きい要素を選択する
  2. 選択した要素と未整列のデータの先頭と入れ替える

ソートの流れをイメージするため、実際に[3, 8, 1, 2]を昇順にソートしてみましょう。

データの下に記載している[0]や[1]はデータの位置を示します。
プログラムはデータの先頭を1番ではなく0番と認識するので、それにあわせて0番から記載しています。

まず未整列のデータの中から一番小さな値を探します。
一番小さな値は2番目にある1です。

このデータと未整列のデータの先頭を入れ替えます。

これで0番目は1に決まりました。

また未整列のデータの中から一番小さな値を探します。
一番小さな値は3番目にある2です。

このデータと未整列のデータの先頭を入れ替えます。

これで1番目は2に決まりました。

また未整列のデータの中から一番小さな値を探します。
一番小さな値は2番目にある3です。

このデータは既に未整列のデータの先頭です。
入れ替えてもデータの並びは何も変わりません。
これで2番目は3に決まり、最後に残った8は末尾の3番目に決まります。

このように選択ソートでは未整列のデータの中から一番小さい要素を選択し、選択した1番小さい要素と未整列の先頭データの入れ替えを繰り返します。

コード

コードにするとこのようになります。
1行ずつ確認していきましょう。

def selection_sort(data):
    length = len(data)
    for index in range(0, length - 1):
        min_index = index

        for pos in range(index + 1, length):
            if data[pos] < data[min_index]:
                min_index = pos
        
        data[index], data[min_index] = data[min_index], data[index]
    
if __name__ == '__main__':
    data = [3, 8, 1, 2, -1, -10, 4, 2]
    selection_sort(data)
    print(data)

コード解説

1行目

まず1行目で挿入ソートを実行するselection_sortメソッドを定義します。
引数にソートしたいデータ(data)を受けとります。

2行目

2行目でソートしたいデータの数をlengthに入れています。
なぜデータの数が必要か考えていきましょう。
先ほど[3, 8, 1, 2]を昇順でソートした操作をまとめてみます。

  1. 未整列のデータの中から一番小さな値1を選択し、0番目(先頭)の要素3と入れ替える。
    この時点で整列済みのデータは[1]、未整列のデータは[8, 3, 2]。
  2. 未整列のデータの中から一番小さな値2を選択し、1番目の要素8と入れ替える。
    この時点で整列済みのデータは[1, 2]、未整列のデータは[3, 8]。
  3. 未整列のデータの中から一番小さな値3を選択し、2番目の要素を3に入れ替える。(データの並びは何も変わらない。)
    この時点で整列済みのデータは[1, 2, 3]、未整列のデータは[8]。
  4. 最後に残った8は末尾の3番目に決まる。
    この時点で整列済みのデータは[1, 2, 3, 8]となり、全てのデータのソートが完了。

最後の操作4では残った要素が必然的にデータの末尾に決まったためソートしていません。
実際にソートしているのは操作1~3ですので、[3, 8, 1, 2]のデータをソートするには3回の操作が必要です。
つまり4個のデータをソートするには3回の操作が必要となります。

ではデータが[3, 8, 1, 2, 6]の場合は何回の操作が必要でしょうか?
この場合も同じように操作をまとめてみます。

  1. 未整列のデータの中から一番小さな値1を選択し、0番目(先頭)の要素3と入れ替える。
    この時点で整列済みのデータは[1]、未整列のデータは[8, 3, 2, 6]。
  2. 未整列のデータの中から一番小さな値2を選択し、1番目の要素8と入れ替える。
    この時点で整列済みのデータは[1, 2]、未整列のデータは[3, 8, 6]。
  3. 未整列のデータの中から一番小さな値3を選択し、2番目の要素を3に入れ替える。(データの並びは何も変わらない。)
    この時点で整列済みのデータは[1, 2, 3]、未整列のデータは[8, 6]。
  4. 未整列のデータの中から一番小さな値6を選択し、3番目の要素8と入れ替える。
    この時点で整列済みのデータは[1, 2, 3, 6]、未整列のデータは[8]。
  5. 最後に残った8は末尾の4番目に決まる。
    この時点で整列済みのデータは[1, 2, 3, 6, 8]となり、全てのデータのソートが完了。

今回も最後の操作5では、残った要素が必然的にデータの末尾に決まったためソートしていません。
実際にソートしているのは操作1~4ですので、[3, 8, 1, 2, 6]のデータをソートするには4回の操作が必要です。
つまり5個のデータをソートするには4回の操作が必要となります。

まとめると、先頭から末尾以外の要素を1つずつ決めていくため、末尾以外のデータの要素の数がソートする回数となります。
つまりソートしたいデータの要素数とソートする回数の関係は、「ソートする回数 = ソートしたいデータの要素数 – 1」と表せます。

このように、必要な操作の回数を知るためにデータの要素数が必要なので、2行目でデータの要素数をlengthに入れています。

3~10行目

3行目にforループが登場し、4~10行目の処理は全て3行目のforループの中で行われるのでまとめて見ていきましょう。

forループの事前知識として、Pythonでは for index in range(0, 5):と書くことで index は0, 1, 2, 3, 4の値をとり、5回ループします。
つまり3行目でfor index in range(0, length – 1)と書くことで先ほど見たように「ソートする回数 = ソートしたいデータの要素数 – 1」となります。

では1行ずつコードを追っていきましょう。
イメージしやすいように、操作とデータの状態を図で表していきます。
まず3行目のループですが、indexは0から始まります。

4行目でmin_indexにindexの値を入れます。

次に6行目のループが開始します。
range(index + 1, length)の範囲でループするので、posはindex + 1から開始します。

7行目のコードでdata[pos]とdata[min_index]の大小を比較します。
今回はdata[pos]が8でdata[min_index]が3です。
data[pos]よりdata[min_index]の方が大きければ8行目の処理を実行しますが、data[pos]よりdata[min_index]のほうが小さいので8行目の処理は行いません。

6行目のループが2巡目に移り、posが1大きくなります。

7行目のコードでdata[pos]とdata[min_index]の大小を比較します。
今回はdata[pos]が1でdata[min_index]が3です。
data[pos]よりdata[min_index]の方が大きいので8行目の処理を実行します。
8行目のコードでmin_indexにposの値を入れます。

6行目のループが3巡目に移り、posが1大きくなります。

7行目のコードでdata[pos]とdata[min_index]の大小を比較します。
今回はdata[pos]が2でdata[min_index]が1です。
data[pos]よりdata[min_index]のほうが小さいので8行目の処理は行いません。

posがデータの末尾まで来たので6行目のループは終了です。
これでmin_indexの値が決まります。

最後の10行目でdata[index]とdata[min_index]の値を入れ替えます。

これで3行目のループの1巡目が終わり、先頭の値が決まります。

3行目のループが2巡目に入ります。
indexは1増えるので以下のようになります。

4行目でmin_indexにindexの値を入れます。

6行目のループが開始します。
posはindex + 1から開始します。

7行目のコードでdata[pos]とdata[min_index]の大小を比較します。
今回はdata[pos]が3でdata[min_index]が8です。
data[pos]よりdata[min_index]大きいので8行目の処理を行います。
8行目のコードでmin_indexにposの値をいれます。

6行目のループが2巡目に移り、posが1大きくなります。

7行目のコードでdata[pos]とdata[min_index]の大小を比較します。
今回はdata[pos]が2でdata[min_index]が3です。
data[pos]よりdata[min_index]大きいので8行目の処理を行います。
8行目のコードでmin_indexにposの値をいれます。

posがデータの末尾まで来たので6行目のループは終了です。
これでmin_indexの値が決まります。

最後の10行目でdata[index]とdata[min_index]の値を入れ替えます。

これで3行目のループの2巡目が終わりました。
3巡目以降も同様の操作を繰り返すことで全てのソートが完了します。

選択ソートでは昇順に並べる場合以下の操作を繰り返しました。

  1. 未整列のデータの中から一番小さい要素を選択する
  2. 選択した要素と未整列のデータの先頭と入れ替える

6~8行目が操作1にあたり、10行目が操作2にあたります。

今回は昇順にソートしましたが、もし降順にソートしたい場合は、7行目のコードの「<」を「>」に変えます。

  • 昇順の場合の7行目
    if data[pos] < data[min_index]:
  • 降順の場合の7行目
    if data[pos] > data[min_index]:

以上で全てのコードの解説が終了です。

実行結果

コードを実行して昇順にソートされることを確認しましょう。

ちゃんと昇順にソートされていますね。
降順にソートする場合も、一度試してみてくださいね。

計算量

最後にデータ数をNとした時の計算量をO記法で表現してみましょう。
(O記法については以前学んだO記法の説明を参考にしてください。)

選択ソートのコードの中で、ソートするデータ数によって計算量が変わるところはどこでしょうか。

まず3行目のfor index in range(0, length – 1)ですね。
range(0, length – 1)となっているため、0からlength – 1の範囲でループします。
つまりループする回数はlengthの値によって変わります。
lengthには2行目でデータ数(len(data))を入れているため、ループの回数はデータ数によって変わります。
つまりデータ数が増えれば増えるほどループの回数も増えるため、ループ数はデータ数に比例しています。

次に6行目のfor pos in range(index + 1, length)です。
こちらも3行目と同じようにforでループしており、range(index + 1, length)の範囲でループします。
同じようにループする回数はlengthで変わります。
lengthにはデータ数(len(data))が入っているため、6行目のループ数もデータ数によって変わります。
つまり、6行目のループもデータ数が増えれば増えるほどループの回数も増えるため、ループ数はデータ数に比例しています。

まとめると、3行目と6行目のfor文はループの回数がデータ数に比例しています。
また、6行目のループは3行目のループにネストしています。
(このネストした計算量の説明はバブルソートの計算量のところで解説しています。
もしよく分からなければそちらを参考にしてみてください。)

つまり選択ソートの計算量はO(N) x O(N) = O(N2)となります。

最後に

以上、第7回目は選択ソートについてでした。
基本のアルゴリズムですので、しっかり理解しておきましょう。

以下の記事で他のソートアルゴリズムについても解説しています。
興味があれば読んでみてください。

以下では探索アルゴリズムを解説しています。
こちらも基本のアルゴリズムとなりますので、しっかり理解しておきましょう。

分かりにくいところや「もっとこうしてほしい」などのご意見がありましたら、ツイッターから連絡いただけると幸いです。
質問に関してもお気軽にお問い合わせください。

私は独学で以下の本からPythonを学びました。
上が初級者向けで下が中級者向けといった感じです。
気が向いたら立ち読みでもしてみてください。

コメント

タイトルとURLをコピーしました