Python基礎講座の第7回目です。
選択ソート(Selection Sort)について解説します。
基本情報技術者試験にも出題される基本的なアルゴリズムなので、しっかり理解していきましょう。
選択ソートとは
選択ソートはソートアルゴリズムの1つです。
（ソートアルゴリズムについては第5回の「ソートアルゴリズムとは」で説明しています。）
選択ソートでは以下を繰り返してデータを並べ替えます。
・昇順（小さい順）に並べる場合
- 未整列のデータの中から一番小さい要素を選択する
- 選択した要素と未整列のデータの先頭と入れ替える
・降順（大きい順）に並べる場合
- 未整列のデータの中から一番大きい要素を選択する
- 選択した要素と未整列のデータの先頭と入れ替える
ソートの流れをイメージするため、実際に[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を選択し、0番目（先頭）の要素3と入れ替える。
この時点で整列済みのデータは[1]、未整列のデータは[8, 3, 2]。 - 未整列のデータの中から一番小さな値2を選択し、1番目の要素8と入れ替える。
この時点で整列済みのデータは[1, 2]、未整列のデータは[3, 8]。 - 未整列のデータの中から一番小さな値3を選択し、2番目の要素を3に入れ替える。（データの並びは何も変わらない。）
この時点で整列済みのデータは[1, 2, 3]、未整列のデータは[8]。 - 最後に残った8は末尾の3番目に決まる。
この時点で整列済みのデータは[1, 2, 3, 8]となり、全てのデータのソートが完了。
最後の操作4では残った要素が必然的にデータの末尾に決まったためソートしていません。
実際にソートしているのは操作1~3ですので、[3, 8, 1, 2]のデータをソートするには3回の操作が必要です。
つまり4個のデータをソートするには3回の操作が必要となります。
ではデータが[3, 8, 1, 2, 6]の場合は何回の操作が必要でしょうか？
この場合も同じように操作をまとめてみます。
- 未整列のデータの中から一番小さな値1を選択し、0番目（先頭）の要素3と入れ替える。
この時点で整列済みのデータは[1]、未整列のデータは[8, 3, 2, 6]。 - 未整列のデータの中から一番小さな値2を選択し、1番目の要素8と入れ替える。
この時点で整列済みのデータは[1, 2]、未整列のデータは[3, 8, 6]。 - 未整列のデータの中から一番小さな値3を選択し、2番目の要素を3に入れ替える。（データの並びは何も変わらない。）
この時点で整列済みのデータは[1, 2, 3]、未整列のデータは[8, 6]。 - 未整列のデータの中から一番小さな値6を選択し、3番目の要素8と入れ替える。
この時点で整列済みのデータは[1, 2, 3, 6]、未整列のデータは[8]。 - 最後に残った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巡目以降も同様の操作を繰り返すことで全てのソートが完了します。
選択ソートでは昇順に並べる場合以下の操作を繰り返しました。
- 未整列のデータの中から一番小さい要素を選択する
- 選択した要素と未整列のデータの先頭と入れ替える
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回目は選択ソートについてでした。
基本のアルゴリズムですので、しっかり理解しておきましょう。
以下の記事で他のソートアルゴリズムについても解説しています。
興味があれば読んでみてください。
以下では探索アルゴリズムを解説しています。
こちらも基本のアルゴリズムとなりますので、しっかり理解しておきましょう。
分かりにくいところや「もっとこうしてほしい」などのご意見がありましたら、ツイッターから連絡いただけると幸いです。
質問に関してもお気軽にお問い合わせください。
以下は関連書籍です。
コメント