Pythonを使ったアルゴリズム学習シリーズです。今回は「選択ソート」の概要を図付きで説明し、Pythonでプログラミングする方法を紹介します。また、動作結果をアニメーションで示すことで理解を深めます。
こんにちは。wat(@watlablog)です。ここでは選択ソートのアルゴリズムをPythonで実装することを目標とします！
選択ソートの概要
目標
プログラミングにおいて、既に先人が完成させているはずのアルゴリズムを写経したりして学ぶことがなぜ重要かは「Pythonコードと図解で理解するバブルソートのアルゴリズム」で記載した通りです。
今回はソート（並べ替え）アルゴリズムの中でもバブルソートに次いで有名な選択ソート(Selection sort)について学習します。
選択ソートの目標はバブルソートと同様にデータを昇順、または降順に並べ替えることです。以下に入力データと出力データの関係図を示しますが、選択ソートは最小値（降順の場合は最大値）を探索して順番に並べていく処理を行う特徴があります。
フローチャートとPythonコードの例
図だけでは曖昧なので、フローチャートを以下に示します。
ここで示すminjは最小値を示すデータ指標です（要素の中で最小値が何番目か）。
Loop1はデータの要素数分のループが回ります。しかし最小値探査部分でも明示はしていませんが、探査のためのループ（別のアルゴリズム）も回ることになります。
その後、i番目の要素とminj番目の要素を交換(swap)する処理を行い、ループ終了時にソートが完了します。
以下にdef関数の形式で書いたPythonコードを示します。引数にデータ配列data、dataの要素数nを渡しています。ここではソートのアルゴリズムを学習することが主目的であるため、最小値探査アルゴリズムはnumpyのargminを使いました。
|
1 2 3 4 5 6 7 8 |
import numpy as np # 選択ソートを行う関数(data=配列データ、n=dataの要素数） def selection_sort(data, n): for i in range(n): j = np.argmin(data[i:]) + i data[i], data[j] = data[j], data[i] return data |
以下に本コードの処理アニメーション例をGIF動画で示します。ソート済のデータ（緑色）が左側から確定していくのはバブルソートと同様ですが、バブルソートが隣り合った要素同士で比較していたのに対し、選択ソートはi番目からn番目までの最小値と直接値を交換しているのが特徴です。
「順次最小値をソート済のすぐ隣に持ってくる」というのがシンプルな説明でしょうか？
処理回数とオーダー
上記アニメーションのカウント(グラフ内のcount数)はデータの要素数10で止まっていますが、実際には毎ループで残りの要素数内の最小値（または最大値）を同じくループで探すことになるため、比較や交換といった処理回数はデータ数を\(N\)とすると\(N(N-1)/2\)回行われます。
そのため選択ソートのオーダーは\(O(N^{2})\)となります。
検証のためのPythonコード
先ほどは関数部分のみでしたが、実際に配列を作成して選択ソートアルゴリズムを使ってみるコードを以下に示します（コピペで動くはず）。
サンプルデータはrandomを使ってランダムな数値配列を生成しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
import random import numpy as np # 選択ソートを行う関数(data=配列データ、n=dataの要素数） def selection_sort(data, n): for i in range(n): j = np.argmin(data[i:]) + i # 最小値を探査 data[i], data[j] = data[j], data[i] # 交換 print('i=', i, data) return data # ランダムなサンプルデータを使って関数を実行する y = random.sample(range(5), k=5) print('initial array=', y) y = selection_sort(y, len(y)) |
本コードを実行すると、コンソールにソート前の配列（initial array）とソート途中の配列逐次プリントされます。確かに最後は昇順になっていることを確認しました。
|
1 2 3 4 5 6 |
initial array= [3, 1, 4, 0, 2] i= 0 [0, 1, 4, 3, 2] i= 1 [0, 1, 4, 3, 2] i= 2 [0, 1, 2, 3, 4] i= 3 [0, 1, 2, 3, 4] i= 4 [0, 1, 2, 3, 4] |
ちなみに、「np.argmin」を「np.argmax」に変更することで降順にすることが可能です。
おまけ：選択ソートアニメーション
記事の途中で紹介したアニメーションは以下のコードで処理中の画像をmatplotlibで1つずつプロット保存して作成しました（汎用性は何も考えていないやっつけコードですが…）。
|
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 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
import numpy as np from matplotlib import pyplot as plt x = np.arange(1, 11, 1) y = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] def selection_sort(data, n): count = 0 axis = np.arange(1, 11, 1) # ここからグラフ描画 # フォントの種類とサイズを設定する。 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, 11, 1)) ax1.set_xlim(0, 11) ax1.set_ylim(0, 14) # データプロットの準備。 ax1.bar(axis, data, label='initial') ax1.bar(0, 0, label='operated') ax1.bar(0, 0, label='sorted') plt.text(1, 12, 'count=' + str(count), fontsize=20) # グラフを表示する。 fig.tight_layout() fig.legend() plt.savefig('fig_' + str("{:05}".format(count)) + '.png') plt.close() for i in range(n): count += 1 j = np.argmin(data[i:]) + i data[i], data[j] = data[j], data[i] # ここからグラフ描画 # フォントの種類とサイズを設定する。 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, 11, 1)) ax1.set_xlim(0, 11) ax1.set_ylim(0, 14) # データプロットの準備。 ax1.bar(axis, data, label='initial') ax1.bar([axis[i], axis[j]], [data[i], data[j]], label='operated') ax1.bar(axis[:i], data[:i], label='sorted') plt.text(1, 12, 'count=' + str(count), fontsize=20) # グラフを表示する。 fig.tight_layout() fig.legend() plt.savefig('fig_' + str("{:05}".format(count)) + '.png') plt.close() # ここからグラフ描画 # フォントの種類とサイズを設定する。 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, 11, 1)) ax1.set_xlim(0, 11) ax1.set_ylim(0, 14) # データプロットの準備。 ax1.bar(0, 0, label='initial') ax1.bar(0, 0, label='operated') ax1.bar(axis, data, label='sorted') plt.text(1, 12, 'count=' + str(count), fontsize=20) # グラフを表示する。 fig.tight_layout() fig.legend() plt.savefig('fig_' + str("{:05}".format(count+1)) + '.png') plt.close() return data sort = selection_sort(y.copy(), len(y)) print(y) print(sort) |
まとめ
本記事では、バブルソートに次いで有名な選択ソートを学び、動画を用いた概要の説明と共にPythonによるコードを紹介しました。
選択ソートも\(O(N^{2})\)オーダーで速いソートではありませんが、考え方がシンプルなので他のコードにも応用が効きそうです。
選択ソートも習得しました！いつもはライブラリに頼っているアルゴリズムも、あえて学ぶと頭の体操になりますね！Twitterでも関連情報をつぶやいているので、wat(@watlablog)のフォローお待ちしています！