티끌 모아 태산

기본 개념

• 한 개를 꺼내어 이미 정렬되어 있는 배열 사이에 순서가 맞도록 끼워 넣는 방식이다

• 삽입 정렬의 i번째 단계가 시작될 때에 배열의 맨 처음 i-1개의 키인 A[0:i-2]는 이미 정렬되어 있다

• 여기에 A[i-1]를 삽입하여 A[0:i-1]이 정렬되도록 하는 것이 i번째 단계의 목표이다

• A[i-1]자리에 있던 키가 제자리를 찾을 때까지 A[i-1]보다 큰 값을 갖는 A[i-2], A[i-3], ... 등을 오른쪽으로 한 자리씩 이동시키고 원래 A[i-1]에 있던 키를 이때 생긴 빈 자리에 넣는다

• 이러한 과정을 n-1회 실행하면 배열이 정렬된다

시간복잡도 O(n^2) 

공간복잡도 O(n)

알고리즘

void InsertionSort(int A[], int n){
/* 입력 : A[0:n] - 정렬할 원소가 있는 배열, n - 정렬할 원소의 개수.
          A[0]는 A[1:n]의 어느 값보다도 더 작은 더미 키이다.
   출력 : A[0:n] - A[0]은 더미 키이고, A[1:n]은 정렬된 배열임. */
   int i, j, Value;
   for (i=2; i<=n ; i++){
  	 Value = A[i];
     j=i;
   	 while(A[j-1] > Value) {
   	    A[j] = A[j-1];
         j--;
  	 }
     A[j]=Value;
   }
}   

• 삽입 정렬에서는 키간의 비교 횟수가 키들의 원래 순서에 민감하게 반응한다

• 키가 내림차순으로 이미 정렬되어 있는 경우 가장 많은 비교를 하게 된다

• 삽입 정렬의 최악의 경우에 2+3+...+n = n(n+1)/2 -1 번의 비교를 필요로 한다

• 사용하는 메모리 공간은 배열의 첨자에 쓰이는 변수와 삽일할 키의 값을 잠시 기억하는데 사용하는 변수뿐이므로 제자리 정렬이다

• 두 개의 동일한 값을 가지는 키의 상대적 위치가 정렬 후에도 변하지 않으므로 안정적인 정렬이다.

참고 : 알고리즘 - 이한출판사