モジュールとアルゴリズム#
# 警告メッセージを非表示
import warnings
warnings.filterwarnings("ignore")
モジュールとパッケージ#
説明#
Pythonには組み込み関数が多く用意されているが，Jupyter NotebookでPythonのセッションを開始しても全ての関数が使える状態になっていない。使えるようにするためには，モジュール（modules）やパッケージ（package）と呼ばれるものを読み込む必要がある。２つの違いを簡単にいうと次のようになる。
モジュール（module）は１つのファイル（拡張子が
.py）にまとめられた関数群であり，パッケージは（package）複数つのファイル（拡張子が
.py）で構成されている（フォルダーにまとめられている）
従って，モジュール全体を読み込んだり，あるパッケージの１つのモジュールだけを読み込むということも可能である。授業では，NumPy，SciPy，Pandasを使うが，ここでは例として数学用のmathモジュールとランダム変数生成用のrandomモジュールを取り上げる。
含まれる関数を使うためにはimportを使って読み込む必要がある。モジュールの全てを読み込むとモジュール内の全ての関数が使用可能となる。
Note
更に付け加えると，サブパッケージ（subpackage）とサブモジュール（submodule）がある大きなパッケージもある。次の章で説明するNumpyパッケージを例として挙げることができる。フォルダーのの構成で考えると次のようになる。
package（フォルダー）
|-- __init__.py（ファイル）
|-- module.py（ファイル; 関数が配置）
|-- subpackage（フォルダー）
|-- __init__.py（ファイル）
|-- submodule.py（ファイル; 関数が配置）
ここで__init__.pyはパッケージとサブパッケージのフォルダーに必ず必要なファイルであり，空の場合もあれば関数が含まれる場合もある。
mathモジュール#
名前が示すように数学に関する関数がまとめられているモジュールとなる（詳細はこのリンクを参照）。mathを次のコードで読み込むことができる。
import math
最初の例として平方根を計算してみよう。使う関数名は，square rootの略となるsqrt()。
math.sqrt(4)
2.0
math.sqrtとは「mathモジュールのsqrt」という意味であり，mathをつけるのは他のモジュールの関数sqrtとバッティングしないようにするためである。
モジュール名が長い場合は，短い名前で読み込むことも可能である。
import math as m
m.sqrt(9)
3.0
モジュール内の特定の関数だけを読み込むことも可能である。
from math import sqrt, log # logは自然対数で, sqrtの両方を読み込む
このコードは「mathモジュールからsqrtとlogを読み込む」と読むことができる。
sqrt(10), log(10)
(3.1622776601683795, 2.302585092994046)
ただ、この場合は他のモジュールやパッケージ、もしくは自分が定義した関数をバッティングしないように注意する必要がある。
randomモジュール#
randomモジュールを使うことにより乱数を発生させることができる（詳細はこのリンクを参照）。まずrandomをインポートしよう。
import random
様々な関数が用意されているが，その中のrandint()関数は，引数で指定するランダムな整数を返す。
第１引数：最小値（整数型）
第２引数：最大値（整数型）
次のコードは\([1,10]\)の間の整数を返す。1と10は戻り値に含まれることに注意しよう。
random.randint(1, 10)
では実際にコードを実行してみよう。次のコードはサイコロの目（1~6）を１つを返す。
random.randint(1,6)
1
内包表記を使って10回サイコロを振った結果を表示してみよう。
[random.randint(1,6) for _ in range(10)]
[1, 3, 5, 3, 3, 3, 1, 5, 6, 2]
Note
内包表記に_（アンダースコア）を使っている。iやjを使っても良いが，回数を数える以外に役目はない。その様な場合に良く使われるのが_である。forループでも同じことが言える。次のコードが例として挙げられる。
for _ in range(5):
print('hello')
２行目に_は入っていないので，ループの回数を数える以外の役割はない。
次に，gauss()を紹介する。この関数は，正規分布から生成されたランダム変数を１つ返す。引数は次の様になっている。
第１引数：平均値
第２引数：標準偏差
従って，次のコードは標準正規分布からのランダム変数を生成する。
random.gauss(0, 1)
関数名がgaussなのは，正規分布はガウス分布とも呼ばれるためである。
次のコードは，平均10，標準偏差2からランダム変数を生成している。
random.gauss(10,2)
11.790772847360456
内包表記を使って，標準正規分布から生成された10のランダム変数からなるリストを作成しよう。
[random.gauss(0,1) for _ in range(10)]
[-0.04331655830628346,
0.44051383123259874,
-0.24400368905867742,
0.04447812065432129,
-1.861149407602846,
-1.2315939242606235,
0.24817632206413578,
-0.9499240291267197,
0.22730731206457494,
1.6149587704719548]
アルゴリズム#
コンピューターは0と1で書かれている機械語しか理解できないが，プログラマーにとって機械語は非常に難解である。つまりプログラマーとコンピューターは直接「会話」ができない。この問題を解決するために，プログラミング言語が開発され「通訳・翻訳」の役割を担っている。Pythonを使う場合は，Pythonコードを書き，それをPythonが機械語に「通訳」し，コンピューターが命令を実行することになる。結果が表示されると，プログラマーは内容を確認し，コードを追加・修正などをおこない開発が進んでいく。Jupyter Notebookでコードを書く場合でも同じである。
+--------------+ Pythonが「通訳」 +-------+
| Pythonコード | ▷ ▷ ▷ ▷ ▷ ▷ ▷ ▷ ▷ | 機械語 |
+--------------+ +-------+
▲ ▽
▲ ▽
▲ アルゴリズム ▽ 実
▲ 疑似コード ▽ 行
▲ ▽
▲ ▽
+-------------+ 内容を確認 +-----+
| プログラマー | ◀︎ ◀︎ ◀︎ ◀︎ ◀︎ ◀︎ ◀︎ ◀︎ ◀︎ ◀︎ | 結果 |
+-------------+ +-----+
▶︎：プログラマーがおこなう
▷：コンピューターがおこなう
このサイクルの中でアルゴリズムは，プログラマーがPythonコードを書く際に重要な役割を果たす。日本産業規格（JIS X0001）は次のように定義している。
問題を解くためのものであって，明確に定義され，順序付けられた有限個の規則からなる集合
平たく言えば，コンピューターが実行すると正しい結果が保証された計算手続である。更に，その計算手続きはどのプログラミング言語でも使える問題解決の明確な考え方である。
例えば，カレーを作るとしよう。アルゴリズムはその場合のレシピである。ある程度料理ができる人であれば，書かれている手順に沿って作れば美味しいカレーが出来上がるレシピがアルゴリズムである。様々な問題には異なるアルゴリズムがある。また１つの問題には複数のアルゴリズムが存在する。カレーでも色々なレシピがあるのと同じである。
以下では，比較的に簡単であり，且つ代表的な４つのアルゴリズムについて解説する。また，アルゴリズムによって計算速度が異なり，その理由についても考えることにする。
例１：合計#
次のコードは標準正規分布から抽出した100万個のランダム変数から構成されるリストを作成する。
lst1 = [random.gauss(0,1) for _ in range(10**6)]
このリストの値を合計するためのアルゴリズムを考える。
forループ#
まずforループを使うアルゴリズムを考えてみよう。
def sum_for_loop(lst): #1
x = 0 #2
for i in lst: #3
x += i #4
return x #5
＜コードの説明＞
#1: 引数はイタラブルであるリストを想定している。#2:forループではlstの要素を１つずつxに加算することになるが，その初期値を0とする。#3:forループの開始#4: 累積加算演算子+=を使い要素をxに加算する。#5:forループ終了後にlstの要素の合計であるxを返す。
実際に計算してみよう。
sum_for_loop(lst1)
-142.11001912888452
whileループ#
次にwhileループを使う場合のコードを考えてみよう。
def sum_while_loop(lst): #1
x = 0 #2
idx = 0 #2a
while idx < len(lst): #3
x += lst[idx] #4
idx += 1 #4a
return x #5
＜コードの説明＞
#1: 引数はイタラブルであるリストを想定している。#2:forループのxと同じ役目をする。#2a:whileループでは，lstの要素を抽出する際にインデックス番号を使うことになるが，idx（indexの略）はインデックス番号を捉えている。lstの最初の項から抽出するために初期値を0としている。#3:whileループが開始され，idx<len(lst)がFalseとなる時点でループは終了する。例として，lst=[0,10,20]としてみよう。len(lst)は3を返すことになり，idxが3になるとidx<len(lst)がFalseとなるため，その時点で（#5以下は実行されずに）whileループは終了する。#4:lst[idx]ではlstのidx番目の要素を抽出し，それを+=を使いxに加算する。#4a: 次のループでlstの次の要素を抽出できるようにidxを1増やしwhileループを継続する。#5:forループ終了後にlstの要素の合計であるxを返す。
実際に計算してみよう。
sum_while_loop(lst1)
-142.11001912888452
forループと同じ値となっていることが確認できる。
実行スピード比較#
次に２つのコードの終了までの時間を比較してみよう。ここではマジック・コマンドと呼ばれる%timeitを使うが，使い方は簡単で行頭に%timeitと半角スペースを置いて実行コードを書くだけである。まずsum_for_loop()関数を実行してみよう。
%timeit sum_for_loop(lst1)
54.6 ms ± 1.67 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
表示される結果は，使うPCのスペックなどによって若干異なることになる。 結果の解釈方法を説明するため，次のような結果になったとしよう。
MMM ms ± NNN µs per loop (mean ± std. dev. of YYY runs, XXX loops each)
次のように解釈する。
コードを
XXX回実行する試行をYYY回おこない（合計でXXX\(\times\)YYY回），その結果の平均であるmeanはMMM msであり，標準偏差であるstd. dev.はNNN µsである。ここでms：ミリ秒（1/1000秒）µs：マイクロ秒（1/1,000,000秒）ns：ナノ秒（1/1,000,000,000秒; 10億分の１秒）
試行する度に結果が異り，その変動を標準偏差で捉えている。結果は正規分布に従うと仮定すると，約68％の結果が平均\(\pm\)標準偏差の範囲内に収まることになる。
次にsum_while_loop()の速度を計測してみよう。
%timeit sum_while_loop(lst1)
235 ms ± 9.29 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
whileループに比べてforループが約4倍速いことが確認できる。リストから要素を一つずつ抽出し合計するというアルゴリズムでも，コードにどのように表現するかによって速度に大きな違いが発生している。
では，なぜそのような大きな違いがあるのだろうか。それは次の２つの違いに起因する。
sum_for_loop()とsum_while_loop()の#3を考えてみよう。前者の場合，ループ毎にlstの要素をiに割り当てることを行なっている。一方，後者では，ループ毎にidx<len(lst)の条件が満たされているかどうかを確認する必要がある。sum_while_loop()では#2aと#4aが追加されており，「割り当て」と言う意味ではsum_for_loop()の#3と同じである。
従って，whileループにはidx<len(lst)がTrueなのかFalseなのかの確認が追加作業となり，それが時間が掛かる要因となっている。
最後に，組み込み関数であるsum()の速度を計測してみよう。
%timeit sum(lst1)
3.97 ms ± 279 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
sum_while_loop()関数よりも6倍以上も速いことが分かる。組み込み関数は様々なトリックを使い最適化されていることが伺える。
Hint
複数行にまたがるコードの実行スピードを計測する場合は，下の例のように%%timeitを１行目に置き，2行目以降にコードを書くと良いだろう。
%%timeit
sum_while_loop(lst1)
print('Pythonは楽しいね(^o^)/')
例２：値の探索#
次のコードは0から999,999までの整数が並ぶリストを作成する。
lst2 = list(range(1_000_000))
ここで考えるのは，999,000がlst2にあるかどうかを確かめることである。具体的には，lst2の最初の要素から一つずつ確認し
見つかれば
1を返す（探索は途中で終了）見つからなければ
-1を返す（最後の要素まで確認する）
関数を考える。
forループ#
forループを使うコードを考えよう。
def search_for_loop(target, lst): #1
for i in lst: #2
if i == target: #3
return 1 #4
return -1 #5
＜コードの説明＞
#1: 引数のtargetは探索する数字であり，lstはイタラブルであるリストを想定している。#2:forループの開始#3〜#4:iがtargetと等しければ1を返し，forループは終了する。#4が実行されると，関数の実行は終わる。これはreturnには，「関数の実行を終了させる」役割があるため。
#5:#4の実行されずにforループ終了した場合にのみ実行され-1が返される。即ち，lstの最後まで探索し，targetがない場合に実行される行である。
実際に計算してみよう。
search_for_loop(999_000, lst2)
1
whileループ#
次にwhileループを使う場合を考えてみよう。
def search_while_loop(target, lst): #1
idx = 0 #2
while True: #3
if idx == len(lst): #4
return -1 #5
elif lst[idx] == target: #6
return 1 #7
idx += 1 #8
＜コードの説明＞
#1: 引数のtargetは探索する数字であり，lstはイタラブルであるリストを想定している。#2:whileループでは，lstの要素を抽出する際にインデックス番号を使うことになるが，idx（indexの略）はインデックス番号を捉えている。#4と#6で使う。lstの最初の項から抽出するために初期値を0としている。#3:whileループの開始。#5もしくは#7が実行されるまでwhileループは継続する。#4〜#5:#4の条件はlstの最後の要素まで確認した場合にのみ満たされる。その場合，-1が返される。#5が実行されると，関数の実行は終わる。これはreturnには，「関数の実行を終了させる」役割があるため。
#6〜#7:lstのidx番目の要素とtargetが等しい場合に1が返される。その時点で関数の実行（whileループも含めて）は終了する。#7が実行されると，関数の実行は終わる。これはreturnには，「関数の実行を終了させる」役割があるため。
#8:#4と#5の条件がFalseであれば，idxを1増加させてwhileループを継続する。
実際に計算してみよう。
search_while_loop(999_000, lst2)
1
search_for_loop()関数とsearch_while_loop()関数の実行スピードを比較してみよう。
%timeit search_for_loop(999_000, lst2)
35.8 ms ± 2.2 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit search_while_loop(999_000, lst2)
186 ms ± 8.39 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
forループよりwhileループは4倍以上遅いことがわかる。もう理由は明らかであろう。search_linear_for()関数ではループ一回毎に１つのif文の条件#3を確認する必要があるが，search_linear_while()では条件が#4と#6の２つがある。この確認作業の回数の差が数字として現れている。このことから分かることは，whileループであっても条件を１つにすれば速度が倍になると言うことである。それを実現するのが次に考える番兵法と呼ばれるアルゴリズムである。
番兵法#
番兵法はwhileループを使うが，次の手続きが必要となる。
リストの最後に探索する値を追加する
search_while_loop()関数との違いはこの点だけである。これにより，実質的にはsearch_linear_while()の条件#4が不要になり実行スピードの高速化される。コードを確認してみよう。
def search_sentinel(target, lst): #1
size = len(lst) #2
lst.append(target) #3
idx = 0 #4
while True: #5
if lst[idx] == target: #6
break #7
idx += 1 #8
if idx < size: #9
return 1 #10
else: #11
return -1 #12
＜コードの説明＞
#1: 引数のtargetは探索する数字であり，lstはイタラブルであるリストを想定している。#2:lstの要素数をsizeに割り当てる。sizeは#9で使うことになる。#3:lstの最後にtargetを追加する。これが「番兵」である。#4:lstの要素を抽出する際にインデックス番号を使うことになるが，idx（indexの略）はインデックス番号を捉えている。#6，#8，#9で使う。lstの最初の項から抽出するために初期値を0としている。#5:whileループの開始。#6〜#7:lstのidx番目の要素とtargetが等しい場合はbreakを発動させwhileを中断する。等しくない場合は#7を実行せずに#8でidxを1増加さる。#3でtarget（番兵）がlstに追加されたので，lstにtargetがなくても#6は必ず満たされてbreakが発動される。これが番兵の役割であり，高速化のための仕込みとなる。#9〜#12:whileループが中断された後に実行される。#9の条件がTrueの場合はlstにtargetが含まれたと言う意味になるため1を返す。一方，#9の条件がFalseの場合（即ち，idxとsizeは等しい場合），idxは番兵のインデックスとなるため-1を返す。
＜breakとreturnの違い＞
breakはループを終わらせるだけであり，関数の実行は続くことになる。既出の
search_for_loop()関数やsearch_while_loop()関数で明らか様に，returnは関数の評価を終了させる役割がある。従って，ループ計算が最後まで終わっていなくても，returnが実行されると関数の実行が終わることにより，その時点でループ計算は終了することになる。
実際に計算してみよう。
search_sentinel(999_000, lst2)
1
実行スピードを計測してみよう。
%timeit search_sentinel(999_000, lst2)
107 ms ± 6.87 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
search_while_loop()関数と比べると約2倍高速化できた。
組み込み関数#
組み込み関数に1もしくは-1を返す関数は見当たらないため，類似するメソッドを考えてみよう。リストには.index()というメソッドが用意されており，引数に要素を指定すると，その要素のインデックス番号を返す。試してみよう。
lst2.index(999_000)
999000
999_000はlst2の999000番目の要素だという意味。実行速度を計測してみよう。
%timeit lst2.index(999_000)
10.6 ms ± 246 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
search_for_loop()関数よりも約2倍速い。最適化されていることが伺える。
例３：最小値の探索#
次のコードは標準正規分布から抽出した100万個のランダム変数から構成されるリストを作成する。
lst3 = [random.gauss(0,1) for _ in range(1_000_000)]
この中から最小値を探索するアルゴリズムを考えてみよう。lst3の全ての要素を確認する必要があるのでforループを使おう。
直接的な探索#
まず，リストの最小値を直接探索するコードを考えてみる。
def search_min(lst): #1
min_ = lst[0] #2
for v in lst[1:]: #3
if v < min_: #4
min_ = v #5
return min_ #6
＜コードの説明＞
#1: 引数lstはイタラブルであるリストを想定している。#2:lstの0番目の値をmin_に割り当てる。#3のforループで更に小さな値が発見されれば，min_の値と入れ替えることにする。#3:lstに対するforループの開始。#2で0番目の要素がmin_に割り当てられているので，forループは1番目の要素から始める。
#4〜#5:vがmin_より小さければmin_に割り当てる。そうでなければ，min_の値は変えない。#6:forループが終わった後（即ち，lstの値を全て確認した後），min_の値を返す。
実際に計算してみよう。
search_min(lst3)
-4.791617968130324
間接的な探索#
リストの要素はインデックス番号を使ってアクセスすることができる。それを利用して，上のコードをインデックス番号を使って間接的に要素にアクセスする場合を考える。即ち，最小値のインデックスを探し，最終的に最小値を返す関数となる。
def search_min_idx(lst): #1
n_lst = len(lst) #2
idx_min = 0 #3
for idx in range(1,n_lst): #4
if lst[idx] < lst[idx_min]: #5
idx_min = idx #6
return lst[idx_min] #7
＜コードの説明＞
#1: 引数lstはイタラブルであるリストを想定している。#2:lstの要素数をn_lstに割り当てる。n_lstは#4で使うことになる。#3:idx_minは最小値の要素のインデックス番号を割り当てる変数として使う。0番目の要素から考えるので，初期値として0を設定している。#4:range(1,n_lst)に対するforループの開始。#3でインデック0がidx_minに割り当てられているので，forループはインデックス1から始める。
#5〜#6:lst[idx_min]は，その時点で最小値となる値である。その値よりlst[idx]が小さい場合，idxをidx_minに割り当てることによりidx_minのインデックス番号を更新する。そうでない場合はidx_minの値は変更しない。 がmin_より小さければmin_に割り当てる。そうでなければ，min_の値は変えない。#7:forループが終わった後（即ち，lstの値を全て確認した後），idx_minに対応する要素を返す。
実際に計算してみよう。
search_min_idx(lst3)
-4.791617968130324
実行スピード比較#
それぞれのコードの実行速度を比べてみよう。
%timeit search_min(lst3)
38.6 ms ± 625 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit search_min_idx(lst3)
109 ms ± 5.67 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
間接的にインデックス番号を使うと実行速度を減速させることになる。
次に組み込み関数であるmin()と比べてみよう。
min(lst3)
-4.791617968130324
%timeit min(lst3)
12.6 ms ± 339 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
直接的な方法より2倍以上高速実行されている。
例４：ソート#
次のコードは0から999までの整数をランダムに並べたリストを作成する。
lst4 = [random.randint(0,1000) for _ in range(1_000)]
このリストを昇順に並び替えるコードを考える。
単純選択ソート#
最初に考えるアルゴリズムである単純選択ソートは次のような考え方に基づいている。
リストには0番目からn-1番目の要素があるとしよう。
要素の数は
nn>1とする。
アルゴリズム（説明をより明確になるようにループを0回目から数える。）
0回目のループ（外側ループ）0番目から最後までの要素の最小値を見つける（内側ループ）最小値を
0番目の要素と入れ替える（値の入れ替え）
1回目のループ（外側ループ）1番目から最後までの要素の最小値を見つける（内側ループ）最小値を
1番目の要素と入れ替える（値の入れ替え）
2回目のループ（外側ループ）2番目から最後までの要素の最小値を見つける（内側ループ）最小値を
2番目の要素と入れ替える（値の入れ替え）
……
n-2回目のループ（外側ループ）n-2番目から最後までの要素の最小値を見つける（内側ループ）最小値を
n-2番目の要素と入れ替える（値の入れ替え）
（注意）n-1回目のループは必要ない。
この手順に基づくコードを確認しよう。
def insertion_sort(lst): #1
n = len(lst) #2
for i in range(n-1): #3
i_min = i #4
for j in range(i+1,n): #5
if lst[j] < lst[i_min]: #6
i_min = j #7
lst[i], lst[i_min] = lst[i_min], lst[i] #8
return lst #9
＜コードの説明＞
#1: 引数lstはイタラブルであるリストを想定している。#2:lstの要素数をnに割り当てる。nは#3と#5で使うことになる。#3: 上の説明にある「外側ループ」に対応している。合計でn-2回のループ計算をおこなう（最後のインデックス番号であるn-1を使ったループを考える必要はないため）。#4:i_minは#5のforループ（上の説明にある「内側ループ」）で見つかる最小値を割り当てる変数のインデックス番号として使う。#5: 上の説明にある「内側ループ」に対応している。iを所与として，i+1からn-1番目までのループとなる（最小値を探索するためには最後まで確認する必要があるため）。#6〜#7:lst[j]がlst[i_min]より小さければjをi_minに割り当てる。そうでなければ，i_minの値は変えない。#8: 上の説明にある「値を入れ替え」に対応している。#5の内側ループが終わった後（即ち，i+1からlstの全ての値を確認した後），lst[i]とlst[i_min]入れ替えている。#9: 外側ループが終わった後，lstを返す。
コードを実行し，最初の10の要素を表示してみよう。
res = insertion_sort(lst4)
res[:10]
[0, 2, 3, 4, 5, 7, 7, 8, 9, 9]
最後の10の要素を表示してみよう。
res[990:]
[993, 994, 995, 996, 996, 996, 998, 998, 999, 1000]
昇順に並んでいることが確認できる。
バブル・ソート#
次にバブル・ソートと呼ばれるアルゴリズムを考えてみよう。手順は次の内容となる。
リストには0番目からn-1番目の要素があるとしよう。
要素の数は
nn>1とする。
アルゴリズム（ここではループを1回目から数える。）
1回目のループ（外側ループ）（以下の手順が内側ループ）
n-2番目とn-1番目（最後）の要素を比べる小さい方を左に，大きい方を右に入れ替える
同じであれば何もしない
n-3番目とn-2番目の要素を比べる小さい方を左に，大きい方を右に入れ替える
同じであれば何もしない
……
1番目と2番目の要素を比べる小さい方を左に，大きい方を右に入れ替える
同じであれば何もしない
0番目と1番目の要素を比べる小さい方を左に，大きい方を右に入れ替える
同じであれば何もしない
これで
0番目の要素は0番目からn-1番目の要素の最小値となる。
2回目のループ（外側ループ）以下の手順が内側ループ
n-2番目とn-1番目の要素を比べる小さい方を左に，大きい方を右に入れ替える
同じであれば何もしない
n-3番目とn-2番目の要素を比べる小さい方を左に，大きい方を右に入れ替える
同じであれば何もしない
……
2番目と3番目の要素を比べる小さい方を左に，大きい方を右に入れ替える
同じであれば何もしない
1番目と2番目の要素を比べる小さい方を左に，大きい方を右に入れ替える
同じであれば何もしない
これで
1番目の要素は1番目からn-1番目の要素の最小値となる。
……
n-2回目のループ（外側ループ）以下の手順が内側ループ
n-2番目とn-1番目の要素を比べる小さい方を左に，大きい方を右に入れ替える
同じであれば何もしない
n-3番目とn-2番目の要素を比べる小さい方を左に，大きい方を右に入れ替える
同じであれば何もしない
これで
n-3番目の要素はn-3番目からn-1番目の要素の最小値となる。
n-1回目のループ（外側ループ）以下の手順が内側ループ
n-2番目とn-1番目の要素を比べる小さい方を左に，大きい方を右に入れ替える
同じであれば何もしない
これで
n-2番目の要素はn-2番目からn-1番目の要素の最小値となる。
完成！
def bubble_sort(lst): #1
n = len(lst) #2
for i in range(n-1): #3
for j in range(n-1, i, -1): #4
if lst[j-1] > lst[j]: #5
lst[j-1], lst[j] = lst[j], lst[j-1] #6
return lst #7
＜コードの説明＞
#1: 引数lstはイタラブルであるリストを想定している。#2:lstの要素数をnに割り当てる。nは#3と#4で使うことになる。#3: 上の説明にある「外側ループ」に対応している。合計でn-1回のループ計算をおこない，lstの全ての要素インデックスに対応している。#4: 上の説明にある「内側ループ」に対応している。range(n-1, i, -1)はi+1からn-1までの番号を逆順に並べている。例えば，list(range(10, 5, -1))は[10,9,8,7,6]を返す。これは#5と#6に置いて最後の要素から始まってからi+1番目の要素までを順に考える必要があるため。#5〜#6:lst[j-1]>lst[j]とは左の要素が右の要素より大きい場合にTrueを返し，その場合，#6では左右の要素を入れ替えている。#6は上の説明の２つの要素の入れ替えに対応している。#7: 外側ループが終わった後，lstを返す。
コードを実行し，最初の10の要素を表示してみよう。
res = bubble_sort(lst4)
res[:10]
[0, 2, 3, 4, 5, 7, 7, 8, 9, 9]
最後の10の要素を表示してみよう。
res[990:]
[993, 994, 995, 996, 996, 996, 998, 998, 999, 1000]
実行スピード比較#
それぞれの実行スピードを比較してみよう。
%timeit insertion_sort(lst4)
57.5 ms ± 4.14 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit bubble_sort(lst4)
78.4 ms ± 2.92 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
スピードの違いの一つの要因は「値の入れ替え」の回数の差である。
insertion_sort()の場合，#8で値の入れ替えがおこなわれており，最大で\(n-1\)回となる。
一方，bubble_sort()の値の入れ替えは#6でおこなわれており，最大で\(n^2/2\)回となる。
\(n>2\)の場合，\(n^2/2>n-1\)となるため，実行時間の差に現れていると考えられる。
最後に組み込み関数sorted()と比較してみよう。
%timeit sorted(lst4)
6.22 µs ± 109 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
平均の単位はmsではなくµsとなっている。やはり組み込み関数は速い！