🙆

【Python】バブルソートを使ってみた。

2023/05/14に公開

はじめに

バブルソートとは、リスト内の要素2つを前から順に見ていき、大きいものが右側になるように並べ替えていくものです。

実装

bubble_sort.py
# バブルソート:隣同士を比較する → 最後まで繰り返す → 始めに戻り、隣同士を比較 → 最後から2番目まで繰り返す
from typing import List

# 関数の定義(入力:元のリスト、出力:並べ替えた後のリスト)
def bubble_sort(numbers: List[int]) -> List[int]:
    # リストの長さを求める
    len_numbers = len(numbers)
    # リスト内の要素の個数分、インデックス番号を用意する
    for i in range(len_numbers):
        # 隣同士を比較できるのは最後から2番目まで、最後まで行ったらソートをかける範囲をiの分だけ狭める
        for j in range(len_numbers - 1 - i):
            # 大きさを比較する(手前の数値のほうが大きければ、入れ替える)
            if numbers[j] > numbers[j+1]:
                numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
    return numbers

# for文を2回使用しているので、O(NN^2オーダー)

# テスト
if __name__ == "__main__":
    # テスト用のランダムな数値を作成する
    import random
    nums = [random.randint(0, 100) for _ in range(10)]
    # ソート後のリストをプリントする
    print(bubble_sort(nums))

参考

https://www.udemy.com/course/python-algo/

Discussion