Pythonのバブルソートとは何ですか？例を挙げて説明しますか？

バブルソートは、リストを昇順（または降順）にソートするためのソートアルゴリズムです。これは最も簡単な並べ替えアルゴリズムですが、あまり効率的ではありません。小さい入力サイズで使用できますが、長さが長いリストや配列では時間効率が良くありません。その時間計算量はO（n ^ 2）です。ただし、これはインプレース並べ替えアルゴリズムであるため、余分なスペースは使用されません。したがって、スペースの複雑さの点で効率的です。ただし、バブルソートよりも優れたソートアルゴリズムがあるため、あまり使用されません。

バブルソートはどのように機能しますか？

バブルソートでは、2つのforループが使用されます。外側のforループは、リストを繰り返し処理します。内側のforループも、すべての外側のループ反復のリストを反復処理します。

バブルソートの主な操作は、2つの連続する要素を比較することです。最初の要素が次の要素よりも大きい場合は、両方を交換して、小さい方の要素が先に進み、大きい方の要素が戻るようにします。外側のループを1回繰り返すと、リストの最大の要素が最後のインデックスに移動します。外側のループの2回目の反復では、リストの2番目に大きい要素が最後から2番目のインデックスに移動します。したがって、すべての反復の最後にソートされたリストを取得します。

例を参考にして理解を深めることができます。

例

次のリストを並べ替える必要があります。

外部ループ=1

5> 2、したがって両方を交換します

5> 1、したがって両方を交換します

5> 3、したがって両方を交換します

5> 4、したがって両方を交換します

（最大の要素5は、最初の外部反復後の最後のインデックスに到達しました）

外部ループ=2

2> 1、したがってスワップ

交換は必要ありません

交換は必要ありません

ご覧のとおり、リストは2番目の外側の反復自体でソートされています。ただし、外側のループはさらに3回繰り返され、それ以上のスワップ操作は行われません。したがって、この例では2回の反復のみが示されています。場合によっては、リストは最初の反復自体でソートできます。場合によっては、最後の反復でリストがソートされることがあります。したがって、外側のループは常にn回繰り返されます。

例

def bubble_sort(arr):
   for i in range(len(arr)):
      for j in range(len(arr)-1):
         if(arr[j]>arr[j+1]):
            temp=arr[j]
            arr[j]=arr[j+1]
            arr[j+1]=temp
   return arr
array=[2,3,1,5,4]
print(bubble_sort(array))

出力

[1, 2, 3, 4, 5]