정렬 알고리즘 - 삽입 정렬[Insert sort]

정렬 알고리즘 중 하나인 삽입 정렬[insert sort]에 대해 설명드리겠습니다.

 

 

[삽입 정렬 이란??]

 

정렬 알고리즘 중 하나로

임의의 데이터를 이미 정렬되어 있는 일정 부분에 적절한 위치를 결정해 삽입해가면서

정렬하는 알고리즘입니다.

 

 

[선택 정렬 예시]

 

표를 통해 간단한 예시를 만들어 보았습니다.

 

정렬되지 않은 데이터 [13, 10, 2, 4, 8]

13

10

2

4

8

 

두 번째 데이터 10과 앞에 위치한 13의 크기를 비교합니다.

두 개의 데이터 중 10의 크기가 작으니 앞으로 한 칸 보내고 13은 10이 있던 자리로 보냅니다.

10

13

2

4

8

 

세 번째 데이터 2와 앞에 위치한 10, 13 두 개의 데이터를 비교합니다.

2가 가장 작으므로 10,13을 한칸씩 뒤로 보내고 2를 맨 앞으로 가져옵니다.

2

10

13

4

8

 

네 번째 데이터 4와 앞에 위치해있는 2, 10, 13 세 개의 데이터를 비교합니다.

데이터 4는 2보다는 크고 10, 13 보다는 작으니 2뒤에 위치시켜줍니다.

2

4

10

13

8

 

마지막에 위치한 데이터 8을 앞에 있는 데이터 2, 4, 10, 13 네 개의 데이터와 비교합니다.

데이터 8은 2,4 보다는 크고 10, 13보다는 작으니 4뒤에 위치시켜줍니다.

2

4

8

10

13

 

그러면 이렇게 데이터들이 작은 데이터부터 차례대로 정렬되게됩니다.

2

4

8

10

13

 

 

 

[소스 코드]

 

#include <stdio.h>
 
 
int main(void)
{
    int arr[5] = { 13,10,2,4,8 };
    int t = 0, j = 0;
    for (int i = 1; i < 5; i++)
    {
        t = arr[i];
        for (j = i - 1; j >= 0; j--)
        {
            if (arr[j] > t)
                arr[j + 1] = arr[j];
            else
                break;
        }
        arr[j + 1] = t;
    }
    printf("정렬 후 숫자 배열\n");
    for (int i = 0; i < 5; i++)
    {
        
        printf("%d ", arr[i]);
    }
}

 

 

[정리]

오늘 정리한 삽입 정렬은 데이터를 적절한 위치에 삽입시키는 방법으로 데이터들을 정렬시킵니다.

그래서 버블 정렬 같은 무조건 위치를 바꿔야 되는 불필요한 상황을 줄여

정렬 알고리즘 중에 속도가 가장 빠르다고 볼 수 있습니다.

 

여기까지 정렬 알고리즘인 버블 정렬, 선택 정렬, 삽입 정렬 3가지 알고리즘을 모두 알아보았습니다.

버블 정렬, 선택 정렬, 삽입 정렬 세 가지 모두 복잡도는 모두 비슷하지만

오늘 정리한 삽입 정렬에서는 연산이 가장 적게 발생되는 것을 알 수 있습니다.

그래서 세 개의 정렬 방법 중 삽입 정렬이 가장 좋은 알고리즘이라고 생각합니다.~:)