Photo by Maarten Duineveld

挿入ソート

概要

わくわくアカデミーは神です。

コード

break 文があり途中で離脱することができます。 バブルソートよりもいくらか速いです。

#
# 対話モード >>> に
# コピペで実行できます。
#
def insertion_sort(lst):
    n = len(lst)
    for i in range(n):
        for j in reversed(range(i)):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
            else:
                break  # <- この break 文がポイント


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

バブルソートと挿入ソート

バブルソートと挿入ソートはコードがとてもよく似ています。 違いは 1 reversed の位置と 2 break の有無です。 挿入ソートは break がある分、for 文から早く抜けることができます。

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]

def insertion_sort(lst):
    n = len(lst)
    for i in range(n):
        for j in reversed(range(i)):  # <- 1) reversed が下に来ている。
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
            else:
                break  # <- 2) この break 文がポイント

Wikipedia が神すぎる...

バブルソートと比較すると、「交換回数」は等しくなる。 しかし、「比較回数」は、バブルソートでは必ずn(n-1) / 2回必要だったが、 挿入ソートはこれ以下で済むため、  挿入ソートの方が高速である。  また、ほとんど整列済みのデータに対しては高速という特徴を持っている。
挿入ソート - Wikipedia (opens new window)

途中結果を表示する。

交換が実行された箇所だけ表示します。

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


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(8)]
insertion_sort(lst)
print(lst)

交換する xx である限り左に進み、 交換しなくても良いところ oo に到達すると右に戻っています。 途中で break していることが見えます。 -- は１度も比較していない要素です。

>>> insertion_sort(lst)
oo oo -- -- -- -- -- --
31 37  6 96 90 50 65 24

   xx xx -- -- -- -- --
31 37  6 96 90 50 65 24

xx xx    -- -- -- -- --
31  6 37 96 90 50 65 24

      oo oo -- -- -- --
 6 31 37 96 90 50 65 24

         xx xx -- -- --
 6 31 37 96 90 50 65 24

      oo oo    -- -- --
 6 31 37 90 96 50 65 24

            xx xx -- --
 6 31 37 90 96 50 65 24

         xx xx    -- --
 6 31 37 90 50 96 65 24

      oo oo       -- --
 6 31 37 50 90 96 65 24

               xx xx --
 6 31 37 50 90 96 65 24

            xx xx    --
 6 31 37 50 90 65 96 24

         oo oo       --
 6 31 37 50 65 90 96 24

                  xx xx
 6 31 37 50 65 90 96 24

               xx xx   
 6 31 37 50 65 90 24 96

            xx xx      
 6 31 37 50 65 24 90 96

         xx xx         
 6 31 37 50 24 65 90 96

      xx xx            
 6 31 37 24 50 65 90 96

   xx xx               
 6 31 24 37 50 65 90 96

oo oo                  
 6 24 31 37 50 65 90 96

>>>