Python でバブルソート

すごくわかりやすい

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_interim_progress(lst, i, j)
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]

#
def print_interim_progress(lst, i, j):
    print(interim_progress(lst, i, j))
    print(lst)
    print()

def interim_progress(lst, i, j):
    """ソートの途中経過を表示するリスト
    
    ['oo', 'oo', '  ', '--', '--']
    [5369, 5577, 3393, 7958, 8263]
    
    ['  ', 'xx', 'xx', '--', '--']
    [5369, 5577, 3393, 7958, 8263]
    
    'oo'  ... 要素を交換しなくてよい
    'xx'  ... 要素を交換しないといけない
    '--'  ... ソート完了している
    '  '  ... ソート完了していない
    """
    log = ['  '] * (i + 1) + ['--'] * (len(lst) - (i + 1))
    log[j] = log[j + 1] = 'xx' if lst[j] > lst[j + 1] else 'oo'
    return log

#
import random
lst = [random.randint(1000, 9999) for i in range(5)]
bubble_sort(lst)
print(lst)

こんな感じで表示してくれます。

>>> bubble_sort(lst)
['xx', 'xx', '  ', '  ', '  ']
[5648, 4307, 5944, 2430, 3586]

['  ', 'oo', 'oo', '  ', '  ']
[4307, 5648, 5944, 2430, 3586]

['  ', '  ', 'xx', 'xx', '  ']
[4307, 5648, 5944, 2430, 3586]

['  ', '  ', '  ', 'xx', 'xx']
[4307, 5648, 2430, 5944, 3586]

['oo', 'oo', '  ', '  ', '--']
[4307, 5648, 2430, 3586, 5944]

['  ', 'xx', 'xx', '  ', '--']
[4307, 5648, 2430, 3586, 5944]

['  ', '  ', 'xx', 'xx', '--']
[4307, 2430, 5648, 3586, 5944]

['xx', 'xx', '  ', '--', '--']
[4307, 2430, 3586, 5648, 5944]

['  ', 'xx', 'xx', '--', '--']
[2430, 4307, 3586, 5648, 5944]

['oo', 'oo', '--', '--', '--']
[2430, 3586, 4307, 5648, 5944]

>>>

◯ 挿入ソート もっと簡単な書き方

O(n²) でいいなら、もっと簡単に書けます。 ただ、書き方は簡単だけど、説明はしづらい。

def sort(lst):
    n = len(lst)
    for i in range(n):
        for j in range(i):
            if lst[j] > lst[i]:
                lst[j], lst[i] = lst[i], lst[j]

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