2015/07/08

Python で基本アルゴリズム:バブルソート

Python でバブルソートを行うコードをご紹介します。

# coding: utf-8

def bubble_sort(li):
    """バブルソートでソートしたリストを返す
    """
    li_sorted = li[:]

    for i in range(0, len(li_sorted)):
        for j in range(1, len(li_sorted) - i):
            if li_sorted[j - 1] > li_sorted[j]:
                swap(li_sorted, j)
                # 確認用に途中経過を表示する場合は次の行のコメントを外す
                # print(li_sorted)

    return li_sorted

def swap(li, index):
    """リストの隣り合った要素 index -1 & index の値を入れ替える
    """
    li[index], li[index - 1] = li[index - 1: index + 1]


if __name__ == '__main__':
    # テスト
    print(bubble_sort([8, 5, 2, 1]))  # => [1, 2, 5, 8]
    print(bubble_sort([1, 5, 3]))     # => [1, 3, 5]

swap の部分は必ずしも切り出す必要はないかと思います。


参考
バブルソート - Wikipedia

0 件のコメント: