Python3でバブルソートをするコードです。
バブルソート
バブルソートは隣り合う要素を比較しながら整列させていくソート方法。
手順は以下の3ステップです。
- 後ろから順に隣り合う要素を比較する。
- 左が右の要素に比べ大きい場合交換。
- 走査範囲を前からひとつ狭める。
3.は走査範囲の中で一番小さい値が先頭に来て比較が不要になるため、範囲を狭めています。 2.の交換を小さい場合にすると、降順になります。
ソートのアニメーション
アニメーションは以下の記事で作成しました。
コード
内側のループ回数が1回ずつ減る、2重のループです。
平均計算量はです。
import random
def babble_sort(arr):
""" バブルソート """
length = len(arr)
for i in range(length):
# 3. 走査範囲を前からひとつ狭める
for j in reversed(range(i+1, length)):
# 1. 後ろから順に隣り合う要素を比較する。
if arr[j-1] > arr[j]:
# 2. 左が右の要素に比べ大きい場合交換する。
arr[j-1], arr[j] = arr[j], arr[j-1]
return arr
if __name__ == "__main__":
# 長さ10のランダムな配列
arr = list(range(10))
src = random.sample(arr, len(arr))
print(src)
# [7, 2, 5, 3, 1, 6, 9, 4, 8, 0]
dst = babble_sort(src)
print(dst)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
値の交換はa, b = b, a
を使って1行で書いています。
Python:ファイルダウンロードの進行状況とファイルサイズを表示する方法。urllib
Pythonschedule2024-02-27
【Python】tqdmでforの進捗状況を表示する
PythonColabolatoryschedule2021-02-16
学習済みの日本語単語ベクトルをColabolatoryで試してみる
自然言語処理PythonColabolatoryschedule2021-02-04
Unity ML-Agentsで新しく学習環境を作る
Unity機械学習C#PythonDeepLearningschedule2021-01-22
27. 内部リンクの除去
自然言語処理100本ノックPythonschedule2020-03-17