[Algorithm#03] | 삽입 정렬(Insertion Sort)

🎓 동빈나님의 강의 실전 알고리즘 강좌 (Algorithm Programming Tutorial)를 듣고 정리한 내용입니다.

 

💻 알고리즘

삽입 정렬(Insertion Sort)

• “각 숫자를 적절한 위치에 삽입하면 어떨까?”
• 삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 방법으로 문제를 해결합니다. 다른 정렬 방식들은 무조건 위치를 바꾸는 방식이었다면 삽입 정렬은 '필요할 때만' 위치를 바꾸게 됩니다.
• 삽입 정렬은 비교적 느린 정렬 알고리즘에 속하지만 쉽게 생각할 수 없는, 조금은 복잡한 구조를 가지고 있습니다.
• 만약 데이터가 위와 같이 '거의 정렬된' 상태라면 어떤 알고리즘이 가장 효율적일까요? 바로 지금 우리가 공부하고 있는 삽입 정렬입니다. 삽입 정렬은 필요할 때에 한해서만 삽입을 진행하기 때문에 데이터가 이미 거의 정렬된 상태에 한해서는 어떤 알고리즘보다도 빠르다는 특징을 가지고 있습니다.

 

📝 문제

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.

1 10 5 8 7 6 4 3 2 9

 

✏️ 소스 코드

#include <stdio.h>

int main(void)
{
    int i, j, temp;
    int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    for (i = 0; i < 9; i++)
    {// 첫 번째 원소는 이동하지 않으므로 총 원소 갯수의 -1만큼 반복
        // 정렬할 원소를 선택 적절한 위치에 삽입할 수 있도록 한다. 
        j = i;
        while (array[j] > array[j + 1])
        {// j는 1씩 빼 나가면서 오른쪽 값과 비교해 왼쪽 값이 더 크다면 
            // Swaping
            temp = array[j];
            array[j] = array[j + 1];
            array[j + 1] = temp;
            j--;
        }
    }

    for(i = 0; i < 10; i++)
    {
        printf("%d ", array[i]);
    }
    return 0;
}

 

⏳ 시간 복잡도

삽입 정렬의 시간 복잡도는 O(N^2)입니다.

삽입 정렬은 기본적으로 '정렬이 되어있다고 가정'을 한다는 점에서 특정한 경우에 따라 굉장히 빠른 속도를 자랑합니다.

일단 소스코드상 반복문이 두 번 들어가있다는 점에서 복잡도는 O(N^2)입니다.

 

📚 참고 사이트

• 동빈나 블로그
• 동빈나 - 실전 알고리즘 강좌 (Algorithm Programming Tutorial)