挿入

整列挿入

2番目の要素から、前(左)の要素と比較し、挿入する位置を指定してから、要素を後ろに移動し、指定した位置に整列資料を挿入します(自分の位置が見つかった場合、後ろの要素は検索されません).

時間の複雑さ

最悪の場合(逆ソート)O(n^2)
最適な場合(1からnの順に配列)O(n)

くうかんふくざつさ

O(n)

長所

単純なアルゴリズム
並べ替えられている場合は、非常に効率的です.
ソートする配列でスワップし、他のメモリ領域を必要としません=>その場でソート(その場でソート)
安定したソート
Sortの選択よりも効率的

短所

最悪の時間複雑度はO(n^2)で効率が低下
バブルや選択ソートと同様に、アレイの長さが長いほど効率が低下します.

public class Insertion_Sort {
 
	public static void insertion_sort(int[] a) {
		insertion_sort(a, a.length);
	}
	
	private static void insertion_sort(int[] a, int size) {
		
		
		for(int i = 1; i < size; i++) {
			// 타겟 넘버
			int target = a[i];
			
			int j = i - 1;
			
			// 타겟이 이전 원소보다 크기 전 까지 반복
			while(j >= 0 && target < a[j]) {
				a[j + 1] = a[j];	// 이전 원소를 한 칸씩 뒤로 미룬다.
				j--;
			}
			
			/*
			 * 위 반복문에서 탈출 하는 경우 앞의 원소가 타겟보다 작다는 의미이므로
			 * 타겟 원소는 j번째 원소 뒤에 와야한다.
			 * 그러므로 타겟은 j + 1 에 위치하게 된다.
			 */
			a[j + 1] = target;	
		}
		
	}
}