泡の位置合わせ

659 ワード
泡の位置合わせ ソートアルゴリズム python テキストリンク
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であるため,あまり用いられない.
[TIL]トラブルシューティング、実戦プロジェクト計画、テストコード、MongoDB
AWSのIAM/CloudWatch/S3