Pythonでソートアルゴリズムの再発明をしてみる: バブルソート

概要

• Pythonでソートアルゴリズムを再発明してみるだけ
• 今回は最も簡単と思われるバブルソートについて再発明する
• 参考サイトのサンプルコードをできるだけ見ずに実装する
• とりあえず昇順ソートのみの対応とする

バブルソートの概要

• あんまり速くないので実用面ではあまり使われない
• シンプルなアルゴリズムなので再発明が容易。勉強目的にはよく使われる
• 安定ソート

基本的な手順

1. リストを走査して隣り合う要素の大小関係を比較し、逆だったら入れ替える
2. 上記手順をリストの終端まで繰り返す
3. 一通り走査が完了したらリストの終端の要素は位置が確定するので処理対象から除外し、上記手順を繰り返す
4. 全ての要素の位置が確定したら完了

ソース

import random

def bubble_sort(lst):
    # 手順全体を繰り返すためのループ。全要素の位置が確定したら抜ける
    # max_indexはリストの終端要素の添字
    # step として-1を指定することで、位置が確定した末尾の要素を除外しながら処理を繰り返す
    for max_index in range(len(lst) - 1, 0, -1):
        # リストを走査するループ。ループ内でi+1 を指すので、ループ回数はリストの要素数より1回少ない
        for i in range(max_index):
            if lst[i] > lst[i+1]:
                # 大小関係が逆なので入れ替え
                lst[i], lst[i+1] = lst[i+1], lst[i]


lst = list(range(10))
random.shuffle(lst)

print("ソート前: " + str(lst))

bubble_sort(lst)

print("ソート後: " + str(lst))

参考サイト

• https://www.codereading.com/algo_and_ds/algo/bubble_sort.html