泡の位置合わせ

Bubbleソートは、互いに結合した要素を比較してソートするアルゴリズムです.

複雑度:O(n^2)

ソートされているかどうかにかかわらず、n個の入力がある場合、n個対各n回、すなわちforゲートが2回回転(交換が発生しなくても比較を継続)し、最適、最悪、平均の場合、O(n^2)の時間複雑度がある.

def bubbleSort(arr):
    n = len(arr) - 1
    for i in range(n):
        for j in range(0, n - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

arr = [64, 34, 25, 12, 57, 93, 1, 123]
bubbleSort(arr)

for文を行うn−1は,常に2つの要素を比較するためである.
2つの要素をつかんで回転し,最後に到達すると配列長−1は実際に必要なすべての比較を完了した.だから-1
2番目のクエリのn-iは、最も右側の要素が最大値を決定できるため、ソートされた要素を繰り返しに含めないため、-iを行います.
Bubbleソートの時間的複雑さは常にn^2であるため,あまり用いられない.