InsertionSort

셋째는 InsertionSort, 삽입 정렬이다.

원리

1. 0부터 끝요소까지 반복한다.( current < N )

2. 현재요소의 제 자리를 찾는 과정이 필요하다.

3. 현재요소( current )가 현재요소 - 1( current - 1 ) 보다 작다면 교환이 일어난다.

특징

1. 많은 교환 횟수를 가진다.

2. 이미 정렬되어진 배열의 경우 n - 1번의 비교연산만 수행할 뿐 더 이상의 교환이나 비교연산이 일어나지 않아 빠르다.

연산시간

1. 최선의 경우 : N - 1번

2. 최악의 경우 :   = n(n-1) / 2 

3. 처음에는 1번 비교하며 N-1번 비교까지 반복한다.

O표기법으로는 O(n^2)이 된다.

코드

//INSERTIONSORT
 
void InsertionSort(int* array, int size)
{
    for(int i = 1 ;i < size ;i++ )        // i == (1 ~ size)
    {
        int temp = array[i];              // 현재값 저장
        int tempidx = i;                  // 현재 인덱스 저장
        for(int j = i ;0 <= (j - 1) && temp < array[j - 1] ;j-- )    // j == (i ~ 0) 
        {                                                            // (j) < (j - 1)이면 교환
            array[j] = array[j-1];
            tempidx = j-1;
        }
        array[tempidx] = temp;            // 값 대입 
    }
}
int const MAX = 5;                        // Max 값
int g_arr[MAX] = { 0, };                  // 배열 초기화
int main()
{
    printf("========정렬전========\n");
    //AscendingNumber(g_arr, MAX);        // 순열 배열 생성
    //DescendingNumber(g_arr, MAX);       // 역순 배열 생성
    RandomNumber(g_arr, MAX);             // 랜덤 배열 생성
 
    PrintNumber(g_arr, MAX);              // 배열 출력
    printf("\n");
    clock_t start = clock();              // 시작 시간
    InsertionSort(g_arr, MAX);            // InsertionSort
    clock_t end = clock();                // 끝 시간
 
    printf("========정렬후========\n");
    PrintNumber(g_arr, MAX);              // 배열 출력
    printf("\nTime : %f\n", ((double)(end - start)) / CLOCKS_PER_SEC);
}

결과

시간

시간은 MAX 값 100,000 을 기준으로 측정하였다.

랜덤 배열 : 10.60
역순 배열 : 18.70
순열 배열 : 0.00056

결론

이미 정렬이 되어 있는경우 비교를 한번만 한다는 점이 인상적이다. ( 다른 정렬의 경우 교환은 안일어나지만 전체적인 비교는 일어난다. )

이점을 이용하면 좋은 알고리즘을 구현할 수 있을 것 같다.