처음하시는 분들을 위한 C언어 기초강의 시즌2 - 38 [정렬 알고리즘(삽입 정렬)]

제 38강) 정렬 알고리즘 - 삽입 정렬

오늘은 정렬 알고리즘의 세번째 시간으로 "삽입 정렬"에 대해서 알아봅니다.

기본적으로 삽입 정렬은 배열에서 사용합니다.

 

 

삽입 정렬이란

(사진 출처 : 위키 백과 - 삽입 정렬)

삽입 정렬은 매 사이클마다 해당 원소가 들어가야할 위치를 찾아서 삽입하기위해 나머지를 뒤로 미루는 정렬입니다.

 

매 사이클마다 차례대로 변수를 선택합니다.

그리고 해당 변수를 임시의 변수공간에 두고 해당 변수의 앞에 있던 변수들과 비교를 해가며 위치를 찾아갑니다.

이렇게 본다면 선택정렬과 유사합니다.

단지 선택정렬은 위치는 정해져 있고 변수값을 찾아가지만, 삽입정렬은 변수값은 정해져있고 위치를 찾아간다는 점이죠.

(알고리즘 시험보기 위해서 저는 위와 같이 외웠습니다.)

 

이렇게 되어 삽입 정렬의 비교 횟수 또한 T(n) = n(n - 1) / 2 를 성립하게 됩니다.

그리하여 시간 복잡도 O는 O(n(n - 1) / 2) = O(n^2) 이 됩니다.

 

정렬명	시간 복잡도	메모리 사용
삽입 정렬	O(n^2)	n

이때 메모리는 기존의 n만큼 할당된 배열 그대로 사용하기 때문에 그대로 n만큼의 메모리를 사용합니다.

(물론 비교할때 임시변수때문에 n+1만큼 사용한다고 할 수 도 있습니다.)

 

위의 영상은 삽입 정렬을 시각적인 춤으로 표현한 좋은 영상입니다.

꼭 보세요.

 

 

삽입 정렬 구현

이제 삽입 정렬을 구현하여 봅시다.

#include <stdio.h>
 
void printArr(int* arr, int length)
{
    printf("arr: ");
    for (int i = 0; i < length; i++)
    {
        printf("%d", arr[i]);
        if (i + 1 < length)
            printf(", ");
        else
            printf("\n");
    }
    printf("\n");
}
 
void insertSort(int* arr, int length)
{
    int tmp;            // 현재 선택한 위치의 값
    int tmpIdx;            // 현재 선택한 위치
    int tmpChange;        // 값을 서로 바꿔주기위한 임시변수
    int point;            // 값 비교를 위한 변수의 위치 값
    for (int i = 1; i < length; i++)
    {
        tmpIdx = i;        // 현재 위치는 i
        point = i - 1;    // 비교할 위치는 i보다 1작은 위치
 
        while (1)        // 무한 반복
        {
            tmp = arr[tmpIdx];    // 현재 값
            if (tmp < arr[point])    // 현재 선택한 값이 비교위치의 값보다 작으면
            {
                // 단 단계씩 뒤로 값을 무른다
                tmpChange = arr[point];
                arr[point] = arr[point + 1];
                arr[point + 1] = tmpChange;
                tmpIdx = point;    // 그리고 현재 값의 위치를 비교위치의 값으로 변경
            }
            point -= 1;        // 항상 비교위치는 비교가 끝날때마다 1감소
 
            if (point < 0)    // 만약 비교위치가 0보다 작으면
                break;        // whild문 탈출
        }
    }
}
 
int main(void)
{
    int arr[] = { 9, 11, 8, 2, 3 };
    int length = sizeof(arr) / sizeof(int);
 
    printf("[정렬 전 배열]\n");
    printArr(arr, length);
 
    insertSort(arr, length);
    
    printf("[정렬 후 배열]\n");
    printArr(arr, length);
 
    return 0;
}

위의 변수 설명(19 ~ 22번줄)이 잘 이해가 안되신다면

위의 그림과 같이 보시면 이해가 될겁니다.

 

다음 시간에는

이번시간까지 해서 구현하기는 쉽지만 느린 알고리즘을 살펴보았습니다.

 

다음 시간부터는 조금은 어렵지만 성능을 기대할 수 있는 알고리즘을 하나씩 살펴보도록 할겁니다.