[計算量をざっくり理解 ] バブルソートの計算量

バブルソート

バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n²)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

配列の左から「隣り合う要素を比較して、もしソート順になっていない場合は入れ替えを行う」という処理を繰り返すことで、一番右側にソート順で最後にあたる要素を持っていくことができます（これが泡が上にあがる様に見えるのでバブルソートと言うそうです）。次に、一番右端の要素を除いた配列で、配列の左から隣り合う要素を比較して必要なら入れ替えという処理を、最終的に配列の要素が一つになるまで繰り返して、最終的にソートされた配列を得ることができます。

アルゴリズムは、以下の例が分かりやすいです。

バブルソート#動作例

Python でバブルソートを記述してみます。

nums = [8, 4, 3, 7, 6, 5, 2, 1]

# before sort [8, 4, 3, 7, 6, 5, 2, 1]
print('before sort', nums)

# for ループの中に for ループがネストされているので O(n^2)
for i in range(len(nums)):
    for j in range(1, len(nums)-i):
        # ソート順でない場合は値を入れ替える。
        if nums[j-1] > nums[j]:
            nums[j-1], nums[j] = nums[j], nums[j-1]

# after sort [1, 2, 3, 4, 5, 6, 7, 8]
print('after sort', nums)

for ループの中に for ループがネストされており、計算量は\( O (n^2) \) となります。