삽입 성렬(Insertion Sort)

삽입 정렬은 정렬 대상을 두 부분으로 나눠서, 정렬 안 된 부분에 있는 데이터를 정렬 된 부분의 특정 위치에 삽입해 가면서 정렬을 진행하는 알고리즘 입니다. 구현에 도움이 되는 힌트는 다음과 같다. "정렬이 완료된 영역의 다음에 위치한 데이터가 그 다음 정렬대상이다.", "삽입할 위치를 발견하고 데이터를 한 칸씩 뒤로 밀수도 있지만, 데이터를 한 칸씩 뒤로 밀면서 삽입할 위치를 찾을 수도 있다."

#include <stdio.h>
 
void InserSort(int arr[], int n) {
    int i, j;
    int insData;
 
    for (i = 1; i < n; i++) {
        insData = arr[i];
        for (j = i - 1; j >= 0; j--) {
            if (arr[j] > insData)
                arr[j + 1] = arr[j];
            else
                break;
        }
        arr[j + 1] = insData;
    }
}
 
int main(void) {
    int arr[5] = { 5,3,2,4,1 };
    int i;
    InserSort(arr, sizeof(arr) / sizeof(int));
    for (i = 0; i < 5; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

안쪽 for 문에 속한 if else 문의 실행횟수에 대한 식을 세우면 1+2+3+...+(n-2) + (n-1) 입니다. 이것은 O(n^2)입니다.