[알고리즘] 삽입 정렬(Insertion Sort) 알고리즘 개념과 원리에 대해 쉽고 빠르게 공부해보자 [C언어]

삽입 정렬(Insertion Sort) 알고리즘 개념

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

k번째 반복 후의 결과 배열은, 앞쪽 k + 1 항목이 정렬된 상태이다.

 

카드게임을 할때와 유사하게 생각하면 좋다. 새로운 카드를 뽑을 경우 정렬된 카드 사이에 올바른 자리에 삽입하는 원리이다.

 

 

 

삽입 정렬 알고리즘의 동작 원리

- 상입 정렬은 두 번째 값을 시작으로 첫 번째 값과 비교한다. 비교 후에 삽입할 위치를 지정한 후 값을 알맞는 자리에 삽입하여 정렬한다.

- 즉, 두 번째 값을 첫 번째 값과, 세 번째 값은 두 번째, 첫 번째 값과 네 번쨰 값은 세 번째, 두 번째, 첫 번째 값과 비교한다. 이렇게 N번째 값은 첫 번째 값, .... , N-1 번째 값과 비교를 한다.

 

 

 

이미지로 보는 동작 절차

1) a그림에서 3(첫 번째 값)과 7(두 번째 값)을 비교한다. 7은 3과 비교하고 큰 값이니 원래 자리대로 삽입 정렬한다.

2) b그림에서 2(세 번째 값)를 3(첫 번째 값)과 2(두 번쨰 값)과 비교한다. 2는 제일 작으니 첫 번째 값으로 3은 두 번째 값으로 7은 세 번쨰 값으로 삽입 정렬한다.

3) 위의 순서처럼 f번까지 완료하면 모든 정렬이 마무리가 된다. 

 

 

 

 

삽입 정렬 C언어 코드 : 

 

배열 정의한 코드

#include <stdio.h>
 
int main(void) {
    int i, j, temp;
    int arr[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    for(i = 0; i < 9; i++) {
        j = i;
        while(j >= 0 && arr[j] > arr[j + 1]) {
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            j--;
        }
    }
    for(i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }
}

 

값을 입력 받을 수 있는 코드 

#include <stdio.h>
 
int n;
int arr[10];
 
int main(void) {
    int i, j, temp, n;
    scanf("%d", &n);
    for(i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
 
    for(i = 0; i < n; i++) {
        j = i;
        while(j >= 0 && arr[j - 1] > arr[j]) {
            temp = arr[j - 1];
            arr[j - 1] = arr[j];
            arr[j] = temp;
            j--;
        }
        for(j = 0; j <= i; j++) {
            printf("%d ", arr[j]);
        }
        printf("\n");
    }
    return 0;
}

 

 

 

 

삽입 정렬 알고리즘 특징

1. 이미 정렬이 되어있는 배열의 경우 매우 빠른 속도를 가진다.

2. 역순의 경우 최악의 경우가 된다. (이동과 비교 횟수가 N*(N-1)/2로 증가, 교환은 N번)

3. 난수 배열인 경우(일반적인 경우) 선택 정렬보다는 훨씬 효율히 높다.

4. 대충 정렬된 배열의 경우 삽입 정렬은 속도가 굉장히 빠르다.

5. 삽입 정렬의 성능은 O(N^2)이다.

 

 

 

 

 

베타존 : 네이버쇼핑 스마트스토어