挿入ソートについて

先月、Javascript advent calendarで、v8の配列ソートアルゴリズムにおいて、
配列の要素数に応じて挿入ソートとクイックソートを使い分けているという記事を書きました。
v8における配列ソートについて - kakts-log

今回は、挿入ソートについてまとめてみたいと思います。

挿入ソート

挿入ソートとは、ソートアルゴリズムの一種で、ある値をソート済み配列に追加するときに有効な手法です。
in-placeで、配列を書き換えながら行うので、空間計算量は $O(1)$ ですむためメモリ効率がよく、実装が簡単です。計算量は以下の通りになっています。

最悪計算時間 $О(n^2)$
最良計算時間 $O(n)$
平均計算時間 $О(n^2)$

pythonで書いてみると、以下の通りになります。

import sys

# スペース区切りで配列要素を入力
a = [int(a_temp) for a_temp in input().strip().split(' ')]

for pos in range(1, len(a)):
    # 交換対象の値を保持
    value = a[pos]
    # 配列の要素数 - 1 だけinsertがはしる
    i = pos - 1
    while i >= 0 and a[i] > value:
        # 前方の要素のほうが大きい場合は1つ後ろに値をずらしていく
        a[i + 1] = a[i]
        i = i - 1

    #チェックが終わったら 値を適切な位置に代入する
    a[i + 1] = value

print(a)

使うべき状況

配列の要素数が少ない時(20以下くらい) どれくらいの値をもって”少ない”とするかはマシンスペックやプログラミング言語によって異なりますが、だいたい20以下が望ましいようです。
Javascript エンジンのv8においては10以下のときに挿入ソートを採用しています。
配列がほぼソートされている状態の時配列の要素が、ほぼソートされていて、後ろの数要素だけソートされていない状態の場合、挿入ソートのパフォーマンスは非常に良くなります。
理由としては、配列の前方のほうがソートされているため、比較回数を劇的に減らせるためです。
重複する要素が存在する場合
重複する要素がある場合、データスワッピングの回数が減るため、計算量が減ります。

挿入ソートの利点

ソート時に用いるメモリ量が少ないソートにおいて、与えられた配列を直接書き換えていく仕組みなので、配列の要素以外にメモリを使う必要がありません。

計算量の分析

ベストケースの場合、n要素数の配列の場合計算量は $O(n)$ と、線形時間でソートを行うことができます。
しかし、この状況の配列をソートする可能性はほぼないため、インパクトとしては小さいですが、挿入ソートは、
comparison-basedなソートアルゴリズムの中で、唯一、ベストケースの振る舞いを持つソートアルゴリズムとなります。
そして、ソートする配列が重複なしで、ランダムに要素が並べられている場合は計算量が最悪になります。

平均、最悪な場合の計算量は、どちらも $O(n^2)$ となります。

他のソートアルゴリズムとの比較

要素数が少ない、またはほぼソート済みの配列の場合、クイックソートやマージソートよりも勝るので、要素数が少ないときは挿入ソート、それ以外の場合はクイックソートやマージソートを使うケースが多い。
また、挿入ソートの改良版としてシェルソートというものがある。