삽입정렬 Insertion sort

삽입정렬 Insertion sort *key!!

삽입 정렬은 정렬된 앞부분과 정렬 안된 뒷부분으로 나뉜다.
정렬 안된 부분의 첫 요소를 정렬된 부분에 끼워 넣는것(삽입)을 반복한다.
i번째 반복하기 전에 arr[0 .. i-1]은 정렬되어 있다는 사실을 이용한다.
알고리즘의 아이디어는 다음과 같다.

for (i=1; i<n; i++)
  arr[0..i]를 재배열하여 정렬한다.

arr[i]를 arr[0 .. i-1]의 마지막 요소부터 왼쪽 방향으로 하나씩 비교한다.
arr[j] <= arr[i] <= arr[j+1] 인 j 찾는 과정.

j=i-1;
while (arr[j] > arr[i])
  j--;

arr[i]가 key이고, key를 올바른 곳에 삽입하는것이 목표이다.

---

public class Main
{
	public static void main(String[] args) 
	{
	    int[] arr = {7,2,3,22,5,9,1};
	    int n = arr.length;
	    int key, j;
	    for (int i=1; i<n; i++)
	    {
	        key = arr[i]; // arr[1]부터 key.
	        j = i-1; // 왼쪽으로 가면서 비교. 왼쪽은 이미 정렬되어 있음.
	        while(j>=0 && arr[j] > key) // key보다 작은 값 찾기.
	        {
	            arr[j+1] = arr[j]; // 한칸씩 오른쪽으로 당겨서 key넣을 자리 마련.
	            j--;
	        }
  		arr[j+1] = key; // 키 찾은 곳에 삽입.
	    }
	    
	    for (int k=0; k<arr.length; k++)
            {
                System.out.print(arr[k]+ " ");
            }
	}
}

---

시간복잡도
최악의 경우는 배열이 내림차순으로 정렬되어 있을 때 i=1일 때 1번, i=2일때 2번, i=n-1일때 n-1번 비교를 하게 된다.
즉 총 비교 횟수는 1+2+..n-1 = n(n-1)/2 이므로 시간복잡도는 O(n²)이다.
삽입정렬은 배열이 거의 정렬되어 있을 때 사용하기 좋다.