Pythonでの選択ソートの実装方法を解説していく

本日は、Pythonで選択ソートというシンプルで視覚的にわかりやすいソートアルゴリズムを学びます。さっそく始めてみましょう。

セレクションソートアルゴリズム

挿入ソートと同様に、挿入ソートアルゴリズムはリストを2つのパートに分割します。リストの最初の部分はソートされた部分であり、リストの最後の部分はソートされていない部分です。

最初はリスト全体がソートされていないが、反復するごとにリストの最小の項目が検索され（昇順リストの場合）、ソートされた部分に追加される。

どのように行われるかというと、1つずつソートされていない部分の最小の項目を見つけ、正しい位置にある項目と入れ替えるのです。

つまり、最初の反復では、最小の項目は最初の位置にある項目と入れ替わります。2回目の反復では、2番目に小さい項目が2番目の位置の項目と入れ替わります。といった具合に。

Pythonで選択ソートを実装する

以下は、Pythonによる選択ソートの簡単な実装です。

この関数はリストを受け取り、その場でソートを実行していることに注意してください。代わりにソートされたリストを返すようにアルゴリズムを変更するのはとても簡単です。

セレクションソートアルゴリズムのステップを説明します。

このアルゴリズムでは、リストを昇順にソートします。

• 変数 n はリストに含まれる項目の数です。
• ここで、 i は 0 から n - 2 までです。つまり、 i は最初の項目から 2 番目にある項目までを指します。iの役割は、常に次の最小のアイテムが入る場所を指すことです。したがって、iからリストの最後までの最小のアイテムを見つけ、それをi` に配置することになります。
• もし、 i の後に小さい要素が見つからなかったら、 i が正しいアイテムになります。
• これは、 i 以降のすべてのアイテムを指すことになり、その範囲内で最も小さいアイテムを見つける責任を負うことになります。
• つまり、 j は i 以降のすべてのアイテムを指すことになり、その範囲内で最小のアイテムを見つける役割を果たします。
• 内ループの後、iからn – 1までの最小のアイテムが見つかり、それがi` にあるアイテムと交換されて、正しい位置に移動します。
• 外側のループでは、リスト全体がソートされるまで、次の最小のアイテムを次々に選択して配置し続けます。

では、このアルゴリズムを実際に動かしてみて、配列にどのような影響を与えるかを見てみましょう。

ここでは、12, 16, 11, 10, 14, 13という並びを考えてみましょう。
与えられたリストのサイズ(n): 6

12, 16, 11, 10, 14, 13
10, 16, 11, 12, 14, 13
10, 11, 16, 12, 14, 13
10, 11, 12, 16, 14, 13
10, 11, 12, 13, 14, 16
10, 11, 12, 13, 14, 16

• 緑色の数字は、ソートされた数字です。
• 青字の数字は、ソートされていないものの中から最も小さいものです。
• 色のついていないものがソートされることになります。

このアルゴリズムでは、最小のものを見つけてから、正しい位置にあるものと入れ替えていることがわかります。

出力

同じリストをアルゴリズムで実行すると、次のような結果が得られます。

まとめ

この記事では、選択ソートがどのように動作するかを確認し、Pythonでアルゴリズムを実装し、コードの実際の出力を使用して例のドライランを検証しました。

選択ソートは、バブルソートや挿入ソートと同様に、O(n2)の計算量を持っています。これは、入力サイズが2倍になると、アルゴリズムの実行時間が4倍になることを意味し、非効率なソートアルゴリズムであることがわかる。

一般に挿入ソートに比べて効率は劣りますが、理解や実装はより簡単です。選択ソートについて楽しく学んでいただけたら幸いです。また、次のチュートリアルでお会いしましょう。