ついにWATLABブログから書籍「いきなりプログラミングPython」が発売しました！
Pythonで学ぶアルゴリズム、ソート第3段は「挿入ソート」です。挿入ソートは遅いソートに分類されますが、データの初期配置によって処理途中でbreakが効く分バブルソートよりも速くなる可能性があります。ここでは挿入ソートの図解と1からの実装によりそのアルゴリズムを学びます。
こんにちは。wat(@watlablog)です。ここでは並べ替えアルゴリズムの基本である挿入ソートを学びます！
挿入ソートの概要
既に当ブログでは、バブルソートや選択ソートのコードを実際に実装する事でそのアルゴリズムを理解して来ました。
Pythonはプログラミング特有の学習コストが低く（メモリ処理とか）、良い面ばかりではありませんが、初心者がアルゴリズムを学習するツールにはもってこいです。
これまでの記事はこちらをご覧ください。
「Pythonコードと図解で理解するバブルソートのアルゴリズム」
「Pythonで選択ソートのアルゴリズムを実装する方法【動画付】」
この記事では挿入ソート（Insertion sort）を学びます。挿入ソートは既にソート済みのデータの中に、新たに要素を1つずつ挿入する事で並べ替えを行うアルゴリズムです。
この説明を図解すると下図になります。
既にソートされた配列の中で適切な位置を探し、よっこいしょ、と後ろにデータをずらす事で間を空けて挿入する事から挿入ソートという名前が付いています。
動画にすると以下。
…ちょっと動かすとわかりにくいかも？
これまではフローチャート とかを書いていましたが、最近はフローチャートよりもコードを見た方がわかりやすいと感じるようになったため、いきなりPythonコードを書いてみましょう。
挿入ソートを行うPythonコード
以下にコードを紹介します。
挿入ソートは、
- i番目のデータを退避させる。→extract
- 挿入する必要があるか確認する。→最初のif文
- 挿入要であればデータを1つ前にずらす。
- iterator(j)がデータの先頭になった時、もしくはデータが目的の場所に到達した時にbreakで次の処理にいきます。
このようにする事でソートされたデータがごそっとずれたように見えます（実際は1つずつ横にずらしているだけですが）。
Pythonでは以下コードのようにwhile文を使うと効率的かと思います（わかりやすさでif付けたけど、使わない書き方もあるかも）。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
import random # 挿入ソートを行う関数(data=配列データ、n=dataの要素数） def insertion_sort(data, n): for i in range(1, n): extract = data[i] j = i if extract < data[i - 1]: # 挿入する必要がある場合 while True: data[j] = data[j - 1] # データ列を1つずらす j -= 1 if j == 0 or extract >= data[j -1]: break # 条件を満たした場合はbreakで抜ける data[j] = extract print('i=', i, data, 'j=', j) return data # ランダムなサンプルデータを使って関数を実行する y = random.sample(range(5), k=5) print('initial array=', y) y = insertion_sort(y, len(y)) |
上記コードを実行すると出力画面に以下の文がprintされます。iとjの関係をよく確認ください。
|
1 2 3 4 5 |
initial array= [0, 3, 1, 4, 2] i= 1 [0, 3, 1, 4, 2] j= 1 i= 2 [0, 1, 3, 4, 2] j= 1 i= 3 [0, 1, 3, 4, 2] j= 3 i= 4 [0, 1, 2, 3, 4] j= 2 |
処理自体はすごく簡単ですが、残念ながらこの挿入ソートも計算量は\(O(N^{2})\)の遅いソートです。
バブルソートは全てのデータで比較処理を行なっていますが、挿入ソートはbreak文があるのでほとんど整列済みのデータに対しては高速に処理され、かつアルゴリズムがわかりやすい事で短いデータを扱う場合は利用される事もあります。
おまけ：処理途中確認用動画を作るコード
毎度趣味で作っている動画を作成するコードもおまけで紹介します。
以下のコードを実行すると、img_insertion-sortというフォルダに各処理毎のmatplotlibプロット画像が蓄積され、プログラム実行ディレクトリ直下にmovie-insertion-sort.gifが作成されます。
create_gif関数のdurationで動画の速度調整、random.sample()の数値を変更（+matplotlibの軸変更）で任意の速度、データ数で動画が作成可能ですので、是非遊んでみてください。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
import random import numpy as np from matplotlib import pyplot as plt from PIL import Image import os import glob # GIFアニメーションを作成 def create_gif(in_dir, out_filename): path_list = sorted(glob.glob(os.path.join(*[in_dir, '*']))) # ファイルパスをソートしてリストする imgs = [] # 画像をappendするための空配列を定義 # ファイルのフルパスからファイル名と拡張子を抽出 for i in range(len(path_list)): img = Image.open(path_list[i]) # 画像ファイルを1つずつ開く imgs.append(img) # 画像をappendで配列に格納していく # appendした画像配列をGIFにする。durationで持続時間、loopでループ数を指定可能。 imgs[0].save(out_filename, save_all=True, append_images=imgs[1:], optimize=False, duration=20, loop=0) return def plot(data, i, save_dir): # ここからグラフ描画 # フォントの種類とサイズを設定する。 plt.rcParams['font.size'] = 14 plt.rcParams['font.family'] = 'Times New Roman' # 目盛を内側にする。 plt.rcParams['xtick.direction'] = 'in' plt.rcParams['ytick.direction'] = 'in' # グラフの上下左右に目盛線を付ける。 fig = plt.figure() ax1 = fig.add_subplot(111) ax1.yaxis.set_ticks_position('both') ax1.xaxis.set_ticks_position('both') # 軸のラベルを設定する。 ax1.set_xlabel('x') ax1.set_ylabel('y') ax1.set_xticks(np.arange(1, 110, 10)) ax1.set_xlim(0, 101) ax1.set_ylim(0, 100) # データプロットの準備。 ax1.bar(np.arange(1, len(data)+1, 1), data, label='data') plt.text(1, 12, 'count=' + str(i), fontsize=20) # グラフを表示する。 fig.tight_layout() fig.legend() # dirフォルダが無い時に新規作成 if os.path.exists(save_dir): pass else: os.mkdir(save_dir) # 画像保存パスを準備 path = os.path.join(*[save_dir, str("{:05}".format(i)) + '.png']) # 画像を保存する plt.savefig(path) plt.close() return # 挿入ソートを行う関数(data=配列データ、n=dataの要素数） def insertion_sort(data, n): count = 0 for i in range(1, n): extract = data[i] j = i if extract < data[i - 1]: # 挿入する必要がある場合 while True: data[j] = data[j - 1] # データ列を1つずらす j -= 1 if j == 0 or extract >= data[j -1]: break # 条件を満たした場合はbreakで抜ける data[j] = extract plot(data, count, 'img_insertion-sort') count += 1 print('i=', i, data, 'j=', j) return data # ランダムなサンプルデータを使って関数を実行する y = random.sample(range(100), k=100) print('initial array=', y) y = insertion_sort(y, len(y)) create_gif('img_insertion-sort', 'movie-insertion-sort.gif') |
今回は100個のデータでやってみました。
大量のデータがソートされていく様を観察するのはなぜかすっきりするので、ヒーリング効果があるのでは？
まとめ
今回は挿入ソートを紹介しました。
これ系のアルゴリズムは文章を読んだりするだけじゃイマイチ理解できないと思いますので、是非図解や動画、自分でコーディングする事によって身につけてみてください。
…そろそろ遅いソートから次のステップに行ってみたいと思います。
色々なソートのアルゴリズムを学んで基礎力をつけましょう！
Twitterでも関連情報をつぶやいているので、wat(@watlablog)のフォローお待ちしています！