この記事では、Pythonの挿入ソートについて学びます。
このソートアルゴリズムは、実際の生活で物を並べ替える方法と非常によく似た働きをします。
さっそく始めてみましょう。
挿入ソートアルゴリズム
1から10までのカードがシャッフルされた状態で用意され、それを並べ替えるように言われたら、おそらくカードを一枚ずつ手に取り、正しい位置にある別の並べ替えの山に挿入することでしょう。
挿入ソートは、私たちが物を分類するのと同じように、与えられた順序で分類された部分を維持し、分類されていない部分から1つの項目を取り出して、分類された部分の正しい位置に挿入するものです。
はじめに、ソート済みセクションには1つの要素しかなく、それは一番最初のものである（ソート済みセクションはリストの先頭にある）。
ソートされていないセクションがどこから始まるかをインデックスで管理し、ソートされていないセクションは2番目の要素から始まるので、インデックスは1である必要があります（Pythonの場合）。
さて、ソートされていないセクションから最初の要素（ソートされていないインデックスの要素）を取り出し、ソートされたセクションでの位置を見つけようとします。
これは、新しい要素よりも小さい（リストが昇順の場合）または大きい（リストが降順の場合）要素を見つけるまで、ソートされたセクションの各要素と連続的に比較することによって行われます。
次に、その位置に新しい要素を挿入し、新しい要素に合わせてソートされたすべての要素を一旦移動させます。
この記事もチェック：Pythonによるバブルソートの昇順、降順の実装方法とコードを解説する
Pythonでの挿入ソート
Pythonのアルゴリズムは以下のようになります。
def insertion_sort(lst):
for i in range(1, len(lst)):
for j in range(i - 1, -1, -1):
if(lst[j] > lst[j + 1]):
lst[j], lst[j + 1] = lst[j + 1], lst[j]
|
この関数はリストを受け取り、インプレースでソートを実行することに注意してください。
しかし、代わりにソートされたリストを返すようにアルゴリズムを変更するのはとても簡単です。
挿入ソートアルゴリズムの理解
このアルゴリズムがどのように働くか、例題で実行してみましょう。
- 例えば、与えられたリストが 12, 16, 11, 10, 14, 13.
- 与えられたリストのサイズ。6
- 昇順でソートします。
- ここで、
iは1から5までとなり、16から13までのすべての要素が正しい位置に挿入されます。 - 最初のループの中で、
jはi - 1から 0 に移動するので、正しい位置を探す役割を担います。j` は正しい位置を探そうとするため、選択されたアイテムと一緒にリスト内を移動します。 - もし、
jにあるアイテムの方が大きければ、jとj + 1の位置が入れ替わり、アイテムは後方に移動します。 - この後、
jは 1 つずつ減っていき、選択されたアイテムが常にj + 1の位置にあるようにします。 - 最後に、
jの位置の項目が選択された項目より大きくなくなり、選択された項目は正しい位置に移動して、内側のループを終了します。 - 外側のループは、次の項目に対して同じことをします。
順序の変更は次のようになります。
- 緑色の項目は、ソートされたセクションの正しい位置にあることを示します。
- 赤色で表示されているものは、正しい位置に向かって左に移動しながら仕分けされています。
- 色の付いていない項目は、ソートされていない部分です。
出力
同じリストをアルゴリズムで実行すると、次のような結果が得られます。
まとめ
この記事では、挿入ソートが実生活でのソート方法に非常に似ていることを確認し、そのアルゴリズムについて説明し、挿入ソートをPythonで実装しました。
その後、アルゴリズムがどのように動作しているかを議論し、ソートされていない例でアルゴリズムを試行しました。
最後に、実際のコードの出力を使って、ドライランの検証を行いました。
挿入ソートは、バブルソートと同様に、O(n2)の複雑性を持ちます。
そのため、それと同様に、入力サイズが2倍になると実行にかかる時間は4倍になり、3倍になると実行にかかる時間は9倍になる。
このため、実用上は非効率的ですが、非常に直感的に実装できるアルゴリズムです。
挿入ソートについて楽しく学んでいただけたら幸いです。
また次のチュートリアルでお会いしましょう。
この記事もチェック：Pythonでアルゴリズムの時間的複雑性の分析をする方法