挿入ソート [Insertion Sort]
挿入ソートはリストの整列済みの部分に対して新たな要素を適切な位置に挿入することで整列を行うアルゴリズムです。
整列済みのリストの後ろにいくつかの要素を追加して再び整列させるという場合や、一方の整列済みリストに整列されていない他方のリストを追加しながら整列させたい時に威力を発揮します。
アルゴリズム分析
配列を昇順に整列させる場合のアルゴリズムを示します。
- 整列済みのインデックス'A'を決定する
- 'A'の次の要素'B'を整列されていない部分とする
- 'B'を'A'に挿入する
- 'A'と'B'の値を比較して'B'の値が小さければ'A'と交換する
- 'A'と'B'が整列された部分になる
- 'B'の次の要素'C'を整列されていない部分とする
- 整列済みの部分'A','B'に'C'を挿入する
- 隣り合う'C'と'B'の値を比較して'C'の値が小さければ'B'と交換する
- さらに'C'と'A'の値を比較して'C'の値が小さければ'A'と交換する
挿入ソートは常に隣り合う要素で比較、交換を行います。
図解
特徴
挿入ソートは整列されている部分が多ければ多いほど計算量が減り、処理速度は向上します。
反対に、「昇順に整列されたものを降順に並び替える」というように、逆順のリストを対象とした場合にもっとも遅くなります。
サンプルコード
C言語
void insertionSort() が配列を昇順に並び替える挿入ソートの実装です。ソート開始時の整列済みの部分は「配列の先頭のみ」という条件になっています。
また、swap() という値を交換するための関数を作って insertionSort() の見通しを良くしています。
void insertionSort(int numbers[], int array_size)
{
int i, j;
for (i=1; i < array_size; i++) { //整列されていない部分の先頭を指す
j = i; // 交換要素のためのインデックス
// 整列済みの場合は処理しない
while ((j > 0) && (numbers[j-1] > numbers[j])) {
// 整列されていない隣り合う要素を交換する
swap(&numbers[j-1], &numbers[j]);
// 隣り合う要素のインデックスを更新
j--;
}
}
}
void swap(int *p_from, int *p_to) {
int tmp;
tmp = *p_from;
*p_from = *p_to;
*p_to = tmp;
}
挿入ソートのデモンストレーション プログラム: insertion_sort.c
Python
insertionsort_shift() では 一時変数 key を使って、ループの最後に挿入位置に key を挿入します。こちらの実装の方が直感的かもしれません。
insertionsort_swap() のほうはC言語の実装と同じで、条件に一致するあいだは要素を交換させます。
def insertionsort_shift( aList ):
for right in range( 1, len( aList ) ):
key = aList[right]
left = right
while left > 0 and key < aList[left - 1]:
aList[left] = aList[left - 1]
left -= 1
aList[left] = key
return aList
def insertionsort_swap( aList ):
for right in range( 1, len( aList ) ):
left = right
while left > 0 and aList[left] < aList[left - 1]:
aList[left - 1], aList[left] = aList[left], aList[left - 1]
left -= 1
return aList
if __name__ == '__main__':
from random import shuffle
l = range(15)
lcopy = l[:]
shuffle(l)
print('Unsorted')
print l
assert l != lcopy
print ('Sorted')
print insertionsort_shift(l)
assert l == lcopy
