アルゴリズム – 単純挿入法(insertion sort:挿入ソート)

単純挿入法(挿入ソート)について
単純挿入法のイメージ
サンプルコード
1. Tcl
2. Python

単純挿入法(挿入ソート)について

単純挿入法は、未整列のデータの中から要素を順番に取り出して、整列済みのデータ列の適切な位置に挿入していくことで整列を行うアルゴリズムです。

挿入ソートの平均的な実行速度はバブルソートと大差はありませんが、ソートを行う前のデータが昇順や降順にある程度並んでいる場合には、高速な処理が期待できます。

挿入ソートは整列済みのデータに、新しい要素を追加して再び整列を行う場合などに使用します。

単純挿入法のイメージ

以下の図は単純挿入法を使ってデータを小さい順(昇順)に並べ替える様子のイメージです。

[単純挿入法のイメージ]

サンプルコード

単純挿入法のアルゴリズムを以下のプログラミング言語で紹介します。

Tcl
Python

サンプルコードについて

各プログラミング言語の基本的な制御構造とデータ構造を使って記述しています。

必要であれば、for, foreach、リスト、配列などに書き換えたり、関数化を行って練習してください。

Tcl

[サンプル：insertion-sort.tcl]

#!/bin/sh
# the next line restarts using tclsh \
exec tclsh "$0" "$@"

# 単純挿入法(insertion sort:挿入ソート)

#  arr  : 数値リスト
#   n   : 要素数
#   i   : 未整列データの先頭の位置
#  tmp  : 挿入する要素の値
# blank : 空き要素の位置

array set arr {0 40 1 10 2 30 3 50 4 20}
set n [array size arr]

set i 1    ;# 0番目は暫定で整列済みとするので1で初期化する。

while {$i < $n} {
    set tmp $arr($i)
    set blank $i

    # 右にシフトさせる。
    while {$blank > 0 && $arr([expr $blank -1]) > $tmp} {
        set arr($blank) $arr([expr $blank -1])
        incr blank -1
    }
    # シフト後の空スペースに要素を挿入する。
    set arr($blank) $tmp

    incr i
}
parray arr

[実行例]

$ ./insertion-sort.tcl
arr(0) = 10
arr(1) = 20
arr(2) = 30
arr(3) = 40
arr(4) = 50

[補足説明]

右にシフトせさるところは、

blank(空き要素の位置)がゼロより大きいかつ
arr[blank-1] > tmp の関係が続く間

arr[blank-1]の要素を右にシフトします。

イメージ図でいうところの整列済み(水色)の要素値をarr[blank-1] > tmpの関係が続く間、右に１つずつ移動させます。

イメージ図の４回目の部分を見て頂くとイメージしやすいと思います。

Python

[サンプル：insertion-sort.py]

#!/usr/bin/env python3

# 単純挿入法(insertion sort:挿入ソート)

#  arr  : 数値リスト
#   n   : 要素数
#   i   : 未整列データの先頭の位置
#  tmp  : 挿入する要素の値
# blank : 空き要素の位置

arr = [40, 10, 30, 50, 20]
n = len(arr)

print(arr)

i = 1           # 0番目は暫定で整列済みとするので1で初期化する。

while i < n:
    tmp = arr[i]
    blank = i

    # 右にシフトする。
    while blank > 0 and arr[blank-1] > tmp:
        arr[blank] = arr[blank-1]
        blank = blank-1

    # シフト後の空スペースに要素を挿入する。
    arr[blank] = tmp

    i += 1

print(arr)