[대학교 알고리즘] InsertionSort

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; // 마지막에 자리에 비교대상을 넣어준다.
}

}