[Algorithm] C - 삽입 정렬(Insertion Sort)

요약

시간 복잡도 : O(n^2)

• 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하는 정렬 알고리즘
• 정렬되지 않은 데이터가 있을 때 정렬되지 않은 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입
• 정렬이 많이 이루어진 경우 효율적으로 사용 가능
• 정렬에 안정적이고 단순해서 구현이 쉬우나 시간 복잡도가 비효율적임

삽입 정렬(Insertion Srot)이란

삽입 정렬이란 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하는 정렬 알고리즘이다.
정렬되지 않은 데이터가 있을 때 정렬되지 않은 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입하는 개념이다.

위와 같은 정렬되지 않은 배열이 있다고 가정한다. 삽입 정렬은 2번째 요소부터 선택하여 진행한다.
이때 4는 6보다 앞쪽에 위치해야 하므로, 6보다 앞쪽인 첫 번째에 삽이하고, 6을 오른쪽으로 민다.

다음에 3번째 요소 1을 선택해 앞쪽에 삽입한다. 그 이후 일련의 과정이 계속 반복된다.
즉, 아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입한다.

정렬된 구역, 정렬되지 않은 2가지 구역으로 나누고, 정렬되지 않은 요소의 첫 번째부터 정렬된 요소의 구역으로 정렬되는 것을 볼 수 있다.

 

예제 코드

#include <stdio.h>
#include <stdlib.h>

void SelectionSort(int *a, int n);
void Swap(int* num1, int* num2);

int main() 
{
    int i, n;
    int *x;
    
    printf("요소 개수 : ");
    scanf("%d", &n);
    
    x = malloc(sizeof(int) * n);
    
    for(i = 0; i < n; i++) {
        printf("x[%d] : ", i);
        scanf("%d", &x[i]);
    }
    
    SelectionSort(x, n);
    
    printf("오름차순 정렬\n");
    
    for(i = 0; i < n; i++) {
        printf("x[%d] = %d\n", i, x[i]);
    }
    
    free(x);

    return 0;
}

void Swap(int* num1, int* num2) 
{  
    int temp;
    
    temp = *num2;
    *num2 = *num1;
    *num1 = temp;
}

void SelectionSort(int *a, int n)
{
    int i, j;
    
    for(i = 1; i < n; i++) {
        int temp = a[i];
        // 정렬되지 않은 데이터가 없을 때까지 반복
        for(j = i; j > 0 && a[j - 1] > temp; j--) {
            a[j] = a[j - 1];
        }
        // 요소 위치 교환
        a[j] = temp;
    }
}

실행 결과

요소 개수 : 7
x[0] : 22
x[1] : 5
x[2] : 11
x[3] : 32
x[4] : 120
x[5] : 68
x[6] : 70
오름차순 정렬
x[0] = 5
x[1] = 11
x[2] = 22
x[3] = 32
x[4] = 68
x[5] = 70
x[6] = 120

https://github.com/JeHeeYu/Algorithm/tree/main/Sort/Insertion%20Sort

GitHub - JeHeeYu/Algorithm: 알고리즘 문제 풀이

 

 

출처 : Do it! 자료구조와 함께 배우는 알고리즘 입문: C 언어 편