【動画付き】Pythonで挿入ソートのアルゴリズムを実装する方法

  • このエントリーをはてなブックマークに追加

Pythonで学ぶアルゴリズム、ソート第3段は「挿入ソート」です。挿入ソートは遅いソートに分類されますが、データの初期配置によって処理途中でbreakが効く分バブルソートよりも速くなる可能性があります。ここでは挿入ソートの図解と1からの実装によりそのアルゴリズムを学びます。

こんにちは。wat(@watlablog)です。ここでは並べ替えアルゴリズムの基本である挿入ソートを学びます

挿入ソートの概要

既に当ブログでは、バブルソートや選択ソートのコードを実際に実装する事でそのアルゴリズムを理解して来ました。

Pythonはプログラミング特有の学習コストが低く(メモリ処理とか)、良い面ばかりではありませんが、初心者がアルゴリズムを学習するツールにはもってこいです。

これまでの記事はこちらをご覧ください。

Pythonコードと図解で理解するバブルソートのアルゴリズム
Pythonで選択ソートのアルゴリズムを実装する方法【動画付】

この記事では挿入ソートInsertion sort)を学びます。挿入ソートは既にソート済みのデータの中に、新たに要素を1つずつ挿入する事で並べ替えを行うアルゴリズムです。

この説明を図解すると下図になります。

既にソートされた配列の中で適切な位置を探し、よっこいしょ、と後ろにデータをずらす事で間を空けて挿入する事から挿入ソートという名前が付いています。

挿入ソートの説明図

動画にすると以下。
…ちょっと動かすとわかりにくいかも?

挿入ソートの動画の例(データ数10)

これまではフローチャート とかを書いていましたが、最近はフローチャートよりもコードを見た方がわかりやすいと感じるようになったため、いきなりPythonコードを書いてみましょう。

挿入ソートを行うPythonコード

以下にコードを紹介します。
挿入ソートは、

  • i番目のデータを退避させる。→extract
  • 挿入する必要があるか確認する。→最初のif文
  • 挿入要であればデータを1つ前にずらす。
  • iterator(j)がデータの先頭になった時、もしくはデータが目的の場所に到達した時にbreakで次の処理にいきます。

このようにする事でソートされたデータがごそっとずれたように見えます(実際は1つずつ横にずらしているだけですが)。

Pythonでは以下コードのようにwhile文を使うと効率的かと思います(わかりやすさでif付けたけど、使わない書き方もあるかも)。

上記コードを実行すると出力画面に以下の文がprintされます。iとjの関係をよく確認ください。

処理自体はすごく簡単ですが、残念ながらこの挿入ソートも計算量は\(O(N^{2})\)の遅いソートです。

バブルソートは全てのデータで比較処理を行なっていますが、挿入ソートはbreak文があるのでほとんど整列済みのデータに対しては高速に処理され、かつアルゴリズムがわかりやすい事で短いデータを扱う場合は利用される事もあります。

おまけ:処理途中確認用動画を作るコード

毎度趣味で作っている動画を作成するコードもおまけで紹介します。

以下のコードを実行すると、img_insertion-sortというフォルダに各処理毎のmatplotlibプロット画像が蓄積され、プログラム実行ディレクトリ直下にmovie-insertion-sort.gifが作成されます。

create_gif関数のdurationで動画の速度調整、random.sample()の数値を変更(+matplotlibの軸変更)で任意の速度、データ数で動画が作成可能ですので、是非遊んでみてください。

今回は100個のデータでやってみました。

insertion sortの動画

大量のデータがソートされていく様を観察するのはなぜかすっきりするので、ヒーリング効果があるのでは?

まとめ

今回は挿入ソートを紹介しました。

これ系のアルゴリズムは文章を読んだりするだけじゃイマイチ理解できないと思いますので、是非図解や動画、自分でコーディングする事によって身につけてみてください。

…そろそろ遅いソートから次のステップに行ってみたいと思います。

色々なソートのアルゴリズムを学んで基礎力をつけましょう!
Twitterでも関連情報をつぶやいているので、wat(@watlablog)のフォローお待ちしています!

  • このエントリーをはてなブックマークに追加

SNSでもご購読できます。

コメントを残す

*