トップページ > コンテンツ > 数学・アルゴリズム関連メモ > 数学・情報工学的 > ソートの種類 > 挿入整列法

データを先頭から部分的に整列して、もし走査していった後ろの要素の方が小さかった場合には整列済みの要素の適切な位置に挿入することでソートする方法。

最悪比較回数	n(n-1)/2
最小比較回数	N-1
平均計算量	O(N^2)
最悪計算量	O(N^2)

3

1

2

4

6

5

の場合には

1

3

4

2

6

5

の1,3を交換。次に3,4を比較するけれど交換不要のためしない。
次に4と2を比較するが、2の方が小さいので整列済み

1

3

4

に挿入し、

1

2

3

4

6

5

とするような感じで繰り返すことでソートする。

javaで書いてみた

public class Insertion {
public static void main(String[] args) {
	int[] array = {3,2,4,5,6,1};
	Insertion insertion = new Insertion();
	insertion.insertion(array);
	for(int i = 0; i < array.length; i++) {
	    System.out.println(array[i]);
	}
}
public void insertion(int[] array) {
	int temp;
	for(int i = 1; i < array.length; i++) {
                    /*jはiの値が大きくなるまで交換が先に進まない*/
	   for(int j = i - 1; j >= 0; j--) {
		  if(array[j] > array[j+1]) {
                                      /*以下3行は交換*/
			  temp = array[j];
			  array[j] = array[j+1];
			  array[j+1] = temp;
		  }
	   }
	}
}
}

参考：http://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88