삽입정렬 Insertion Sort

삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다 (위키백과 )

사진으로 설명해보자면,

1. 첫번째 인덱스 값인 85를 정렬된 배열(오름차순)의 첫번째 값으로 보고 다음요소(12)로 이동
2. 이전 인덱스 값들과 비교해 이전 요소가 더 큰 값이 있다면 교환(swap)하는 방식이다
3. 그러므로 85>12이기 때문에 85와 12를 swap
4. 그 다음 요소인 59
5. 59<85이므로 swap
6. 59>12이므로 swap하지 않고 12, 59, 85, ... 의 순이 된다
7. 다음요소 45
8. 45<85이므로 swap
9. 45<59이므로 swap
10. 45>12이므로 그대로 → 12, 45, 59, 85, ... 순이 된다.
11. 이것을 마지막 요소까지 반복하면 12, 45, 51, 59, 72, 85로 오름차순 정렬이 된다.

크기에 따라 새로운 인덱스에 값을 삽입하는 형태

[구현 1]

void InsertionSort(int list[], int n){
  int i, j, key;

  // 인텍스 0은 이미 정렬된 것으로 볼 수 있다.
  for(i=1; i<n; i++){
    key = list[i]; // 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사
    // 현재 정렬된 배열은 i-1까지이므로 i-1번째부터 역순으로 조사한다.
    // j >= 0 이어야
    // key 값보다 정렬된 배열에 있는 값이 크면 j번째를 j+1번째로 이동
    j = i;
		while (list[j-1] > key)
			list[j] = list[j-1]; j--;
			if (j==0) break;

    list[j] = key;
  }
}

[구현 2]

void InsertionSort(int A[ ], int n)
/* 입력: A[0:n] , n: 원소의 개수. A[0]: dummy.
출력: A[0:n] : A[0]: dummy, A[1:n]은 정렬된 배열임
*/
// A[0]은 dummy -> 마이너스 무한대로 가정, A[1]은 이미 정렬됐다고 봄
{  int i, j, Value;
	 for (i ＝ 2; i ＜＝ n; i＋＋) { // A[2]부터 반복문 실행
		 Value ＝ A[i];
		 j ＝ i;
		 while (A[j－1] ＞ Value)
			 A[j] ＝ A[j－1]; j－－; // 한 칸씩 땡겨오는 느낌

		 A[j] ＝ Value;
 } 
}