泡の位置合わせ

バブルソートとは?

水の中の泡が上に上がるように、大きな値は後ろに移動する方法です.そして、決定された大きい値を除き、残りの値の大きい値を後ろに送信する.

バブルソートプロセス

配列の先頭から、隣接する2つの要素のサイズを比較し、大きな値を後方に送信します.

は、最大値を後方に送信し、ソートされた大きな値を除いて、1〜2回のプロセスを繰り返す.

バブルソートコード

def bubbleSort(arr):
    for i in range(len(arr)):
        for j in range(1, len(arr) - i):
            if arr[j] < arr[j-1]:
                arr[j-1], arr[j] = arr[j], arr[j-1]
    return arr

print(bubbleSort([3, 2, 6, 8, 1]))

Pythonで書きます.

時間の複雑さ

1回目の繰返しでは,最大値をn回後方に送信し,その値を除いて配列の大きさは徐々に減少し,n+(n−1)+(n−2)+...+2+1=n(n−1)/2であり、O(n^2)の時間的複雑さを有する.発泡ソートはソートの有無を考慮せず,無条件に2元素を比較する方式であるため,最適,平均,最悪の時間複雑度O(n^2)は同じである.

くうかんふくざつさ

アレイ内部で2つの要素を比較・交換する方式であるため,空間的複雑度はO(N)である.

長所

は直感的である.

は、所定のアレイ内部で位置変換を行う方法であり、追加のメモリを必要としない.

この方式をその場ソートと呼ぶ.

短所

時間複雑度O(N^2)は非常に悪い意味です.