Photo by Alejandro Alvarez

バブルソート

概要

すごくわかりやすい

コード

#
# 対話モード >>> に
# コピペで実行できます。
#
def bubble_sort(lst):
    n = len(lst)
    for i in reversed(range(n)):
        for j in range(i):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]


lst = [3333, 5123, 9981, 1243, 7412]
bubble_sort(lst)
print(lst)
# [1243, 3333, 5123, 7412, 9981]

途中結果を表示する。

途中経過を表示するコードを書きました。

#
# 対話モード >>> に
# コピペで実行できます。
#
def bubble_sort(lst):
    n = len(lst)
    for i in reversed(range(n)):
        for j in range(i):
            print_progress(lst, i, j)
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]


def print_progress(lst, i, j):
    print(' '.join(f'{e:2d}' for e in lst))
    print(' '.join(progress(lst, i, j)))
    print()


def progress(lst, i, j):
    prog = ['  '] * (i + 1) + ['--'] * (len(lst) - (i + 1))
    prog[j] = prog[j + 1] = 'xx' if lst[j] > lst[j + 1] else 'oo'
    return prog


import random
lst = [random.randint(0, 99) for i in range(5)]
bubble_sort(lst)
print(lst)

こんな感じで表示してくれます。 oo は交換しなくていいもの。 xx は交換するもの。 -- はソート済みのものです。

>>> bubble_sort(lst)
48 65 52 68 26
oo oo         

48 65 52 68 26
   xx xx      

48 52 65 68 26
      oo oo   

48 52 65 68 26
         xx xx

48 52 65 26 68
oo oo       --

48 52 65 26 68
   oo oo    --

48 52 65 26 68
      xx xx --

48 52 26 65 68
oo oo    -- --

48 52 26 65 68
   xx xx -- --

48 26 52 65 68
xx xx -- -- --

>>> print(lst)
[26, 48, 52, 65, 68]
>>>