最も直感的で習得しやすいソートアルゴリズムの1つであるバブルソートをPythonで実装して勉強してみましょう。
まずはソートそのものを理解し、バブルソートによるソートを知り、最後にPythonでどのように実装するかを見ていきます。
ソートアルゴリズムの重要性
ソートとは何でしょうか？そして、なぜそれが重要なのか？このセクションでは、このような疑問にお答えします。
図書館の本や辞書の単語から、データベースの項目やプロセッサの命令まで、私たちは何度もソートを経験してきました。
“コンピュータサイエンスにおいて、ソートとは物事を順序立てて並べる行為です。
つまり、ソートを行う際には、与えられた順序をどのような基準で並べるかを知っておく必要があるのです。
この記事では、基準を数値と仮定し、与えられた数値の列を並べ替えることにします。
コンピュータサイエンスにおいて、並べ替えの最も重要な目的は、効率的なアルゴリズムを作成することです。
バイナリサーチは例外的に高速な検索アルゴリズムで、ソートされていないオブジェクトのコレクションでは不可能でしょう。
ソートされたデータでは、ほとんどすべての集合演算が非常に高速に動作します。
効率的なアルゴリズムを作る以外に、カードの山を扱うプログラムのように、プログラムの要件が何かをソートすることである場合、ソートは使用されます。
従って、ソートアルゴリズムはプログラマが知っておくべき最も基本的な概念の1つです。
バブルソートアルゴリズムを理解する
炭酸飲料のグラスの中で、中の泡が盛り上がっていく様子を思い浮かべてください。
この泡は、ある並びの中で最大／最小の要素を表し、泡の上昇する動きは、最大／最小の要素が並びの終わり／始まりに移動する様子を表している。
これがバブルソートの仕組みであり、その名の由来でもある。
簡単に言うと、数列を何回も繰り返して、その度に数列の最大／最小の要素が数列の端に来るように、いくつかの要素の組を入れ替えていくのです。
このチュートリアルのために、与えられた配列を考え、数値の大きい順に並べ替えることにします。
12, 16, 11, 10, 14, 13 |
さて、バブルソートのアルゴリズムは、昇順にソートする場合、次のように動作します。
- iはソートした要素の数、またはリストを通過した回数を表し、リストを通過するたびに確実に1つの項目をソートしているからです。
jはリスト内の位置を表すので、jが3だとすると、リスト内の3番目の数字である11のことを指している。 - リストの要素数をnとします。
-
- iを0とします。なぜなら、リストを通過しておらず、どの要素もソートされていないからです。
-
- jを1にすると、最初の位置の番号から始めることになる。
-
- jの位置の数字がj+1の位置の数字より大きい場合、jとj+1の位置の数字を入れ替える必要があります。これは、リストが昇順であるため、前に来る数字が後に来る数字より大きくなることはありえないからです。
-
- jを1つ増やすと、次の数字の組が見えてくる。
-
- jがn-iでなければ手順5へ、そうでなければループを止めて次の手順へ進む。このループでは、入れ替えが発生するたびに、大きい方の要素がリストの末尾に向かって移動していきます。これはバブルソートの動作と同じで、大きい要素がリストの末尾に向かってバブルしていく。iがすでにソートされた要素の数を表す場合、リストの最後のi個の要素は正しい位置にある（ループをi回まわす間にバブルで移動したため）ので、最後のi個の要素をチェックするのは時間の無駄になるだけなので、jがn-iに等しくなった時点でループは終了します。
- iを1つ増やす。jが最後に達したときにループを終了させた場合、リストをもう1回通過し、さらに1つの要素がソートされたことになる。
-
- iがn-1でなければ4へ、そうでなければiでループを止め、次のステップへ進む。お気づきのように、ループは2つあり、内側のjのループでもう1つ要素をソートし、合計でn個の要素をソートすることになります。
- 10.配列はソートされています。
さて、これを与えられたシーケンスで試してみたいと思うかもしれません。
バブルソートの例
与えられた配列。
- 手順1：変数 i と j はソートされた要素と位置を表す。
- 手順2：nは6なので、n = 6とします。
- 手順3：iを0とします。
- 手順4：jを1にセット。
- 手順5：jとj+1の位置を比較し、1の位置（12）の要素は2の位置（16）の要素より大きくない。
- ステップ6：jをインクリメントする j = 2
- ステップ7：j（2）はn-i（6）ではないので、ステップ5へ。
- 手順5：位置2（16）は位置3（11）より大きいので、入れ替え。
- 順番 12, 11, 16, 10, 14, 13
- 手順6：jをインクリメントする j = 3
- ステップ7：3は6ではないので、ステップ5へ。
- 手順5：16は10より大きいので、入れ替えを行います。順番に 12, 11, 10, 16, 14, 13
- ステップ6：jをインクリメント j = 4
- ステップ7：4は6ではないので、ステップ5へ。
- 手順5：16は14より大きいので、入れ替え。順番を決める。12, 11, 10, 14, 16, 13
- ステップ6：jをインクリメント j = 5
- ステップ7：5は6ではないので、ステップ5へ。
- 手順5：16は13より大きいので、入れ替え。順番に 12, 11, 10, 14, 13, 16
- ステップ6：jをインクリメント j = 6
- 手順7：j (6) は n-i (6) と等しいので、手順8に進む。一番大きい要素(16)は最後にあり、確実に1つの要素をソートしていることに注意。
- ステップ8：iを増やす i = 1
- 手順9：i (1) は n-1 (5) ではないので、手順4からすべて繰り返し、ループを続けます、結果として配列の変化は次のようになります。
11, 12, 10, 14, 13, 16
11, 10, 12, 14, 13, 16
11, 10, 12, 14, 13, 16
11, 10, 12, 13, 14, 16
10, 11, 12, 13, 14, 16
10, 11, 12, 13, 14, 16
10, 11, 12, 13, 14, 16
10, 11, 12, 13, 14, 16
10, 11, 12, 13, 14, 16
10, 11, 12, 13, 14, 16
10, 11, 12, 13, 14, 16
この後、iは5となり、n-1となるので、ループは終了し、アルゴリズムは、リストがソートされたことを教えてくれる。
また、アルゴリズムが終了する前にリストがソートされてしまうこともあるようですが、これは与えられた数列がアルゴリズムに渡される前にある程度ソートされていたことを意味しているだけです。
Pythonでバブルソートを実装する
さて、アルゴリズムの準備ができたので、各ステップをPythonで実装していきます。
いくつか注意する点があります。
リストは位置の代わりにインデックスを持ち、インデックスは1からサイズではなく0からサイズ-1になるので、それを調整する必要があります。
def bubble_sort(sequence):
n = len(sequence)
for i in range(n-1):
for j in range(n-i-1):
if(sequence[j] > sequence[j+1]):
sequence[j], sequence[j+1] = sequence[j+1], sequence[j]
|
例として、このアルゴリズムでソートしてみましょう。
このアルゴリズムではリストをその場でソートしていますが、代わりにソートされたリストを返すようにアルゴリズムを変更するのはとても簡単なことです。
まとめ
この記事では、ソートとは何か、どこで使われるかを学び、バブルソートがどのように動作するかを学び、アルゴリズムを考え、Pythonでバブルソートを実装しました。
バブルソートは多くのソートアルゴリズムの一つであり、ベストなものとは言い難いのですが、実装は非常に簡単です。
あまり使われない理由は、このアルゴリズムの計算量がO(n2)だからです。
つまり、リストの要素数が2倍になると、このアルゴリズムを使ってソートするのにかかる時間は4倍になってしまいます。
つまり、データ量が非常に多い場合、このアルゴリズムは非効率的になってしまうのだ。
とはいえ、プログラマーとしてバブルソートを知っておくことは重要であり、何か学んでいただければ幸いです。