バブル整列(Bubble Sort)

1328 ワード
bubblesort アルゴリズム#アルゴリズム# 泡の位置合わせ テキストリンク

バブルソートとは?


2つの隣接する
  • データを比較し、前のデータが後のデータより大きい場合、シフトソートアルゴリズム
  • n個のリストがある場合、最大(n−1)個の論理が適用される.
  • 論理を1回適用するごとに、最大の数字は後から1つ決定されます.
  • 論理は、事前に終了する可能性があります.したがって、論理を適用するときにデータを交換したことがない場合、論理はソートされているので、論理を繰り返し適用する必要はありません.
  • for num in range(len(data list))
    • を繰り返す
  • swap=0(交換されたかどうかを決定する変数を使用)
  • 反復文では、for index in range(len(data list)-num-1)#n-1を1回反復する必要があるため、
  • 反復文で、データlist[index]>data list[index+1]の場合、
  • data_list[index]. data_list[index + 1] = data_list[index + 1], data_list[index]
  • swap += 1
  • 反復文でswap=0の場合、breakは
    • を終了する.
    def bubblesort(data):
    for index in range(len(data) - 1):
        swap = False
        for index2 in range(len(data) - index - 1):
            if data[index2] > data[index2 + 1]:
                data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
                swap = True
        if swap == False:
            break
    return data
    import random

data_list = random.sample(range(100), 50)
print(bubblesort(data_list))

    アルゴリズム解析

  • には2つの繰り返し文->O(𝑛2)
    最悪なのは𝑛∗(𝑛−1)/2
  • が完全に並べ替えられている場合は、O(𝑛)
    • モンゴルDB
    コードを書く[comments after India project]