多くの人にとって、バブルソートはコンピュータサイエンスの授業で初めて耳にしたソートアルゴリズムであろう。
このアルゴリズムは非常に直感的で、コードに「翻訳」するのも簡単です。これは、新しいソフトウェア開発者がアイデアをコンピュータで実行可能な形に変換するのを容易にするために重要なことです。しかし、バブルソートは、配列が既にソートされているかどうかをチェックする場合を除き、すべてのケースで最も性能の悪いソートアルゴリズムの一つであり、クイックソートのようなより効率的なソートアルゴリズムよりも性能が優れていることが多いのです。
バブルソート
バブルソートの考え方は非常にシンプルで、配列中の隣り合う要素のペアを一度に1組ずつ見て、最初の要素が2番目の要素より大きければ位置を入れ替え、そうでなければ単に移動するだけです。例として、配列8, 5, 3, 1, 4, 7, 9をソートしてみましょう。
最初の数字である「8」に注目すると、それが配列の正しい位置に「泡のように」入っていくのがわかります。次に、このプロセスを数字の「5」に対して繰り返し、さらにそれを続けます。
実装
可視化したところで、アルゴリズムを実装してみましょう。今回も非常にシンプルです。
def bubble_sort(our_list):
# We go through the list as many times as there are elements
for i in range(len(our_list)):
# We want the last pair of adjacent elements to be (n-2, n-1)
for j in range(len(our_list) - 1):
if our_list[j] > our_list[j+1]:
# Swap
our_list[j], our_list[j+1] = our_list[j+1], our_list[j]
では、リストを生成して、その上でアルゴリズムを呼び出してみよう。
our_list = [19, 13, 6, 2, 18, 8]
bubble_sort(our_list)
print(our_list)
出力。
[2, 6, 8, 13, 18, 19]
最適化
シンプルな実装はその役割を果たしましたが、ここで2つの最適化を行うことができます。
スワップが行われないとき、それはリストがソートされていることを意味します。しかし、以前に実装されたアルゴリズムでは、本当に必要ないにもかかわらず、リストの残りを評価し続けることになります。これを修正するために、booleanフラグを保持して、前の反復処理でスワップが行われたかどうかをチェックします。
もしスワップが行われなかったら、アルゴリズムは停止するはずです。
def bubble_sort(our_list):
# We want to stop passing through the list
# as soon as we pass through without swapping any elements
has_swapped = True
while(has_swapped):
has_swapped = False
for i in range(len(our_list) - 1):
if our_list[i] > our_list[i+1]:
# Swap
our_list[i], our_list[i+1] = our_list[i+1], our_list[i]
has_swapped = True
もう1つの最適化は、バブルソートが特定の反復処理で最大の要素が配列の最後に来るように動作するという事実を利用するものです。
最初にリストを通過するとき、n番目の位置が最大の要素であることが保証され、2回目に通過するとき、n-1番目の位置が2番目に大きな要素であることが保証され、以下同様です。
これは、連続した反復のたびに、以前より1つ少ない要素を見ることができることを意味する。より正確には、k回目の反復では、最初のn – k + 1個の要素だけを見ればよい。
def bubble_sort(our_list):
has_swapped = True
num_of_iterations = 0
while(has_swapped):
has_swapped = False
for i in range(len(our_list) - num_of_iterations - 1):
if our_list[i] > our_list[i+1]:
# Swap
our_list[i], our_list[i+1] = our_list[i+1], our_list[i]
has_swapped = True
num_of_iterations += 1
時間比較
それでは、timeitモジュールを使って、同じリストを1000回ソートするのにかかる時間を比較してみましょう。
Unoptimized Bubble Sort took: 0.0106407
Bubble Sort with a boolean flag took: 0.0078251
Bubble Sort with a boolean flag and shortened list took: 0.0075207
後者の2つのアプローチでは、リストが非常に短いため、それほど大きな違いはありませんが、大きなリストでは、2番目の最適化が大きな違いを生む可能性があります。
結論
最も非効率的なアプローチとして、バブルソートはn-1回の反復を行い、隣接するn-1組の要素を調べます。このため、最良ケースと平均ケースの両方で、時間計算量はO(n2)となります。O(n2)はソートアルゴリズムとしてはかなりひどいと思われます。
空間計算量はO(1)ですが、他の分野での欠点を補うには十分ではありません。
しかし、ソフトウェア開発の世界や歴史ではまだ大きな位置を占めており、教科書では基本的なソートアルゴリズムについて語るときに、ほとんど言及しないことはない。