250x250
Notice
Recent Posts
Recent Comments
관리 메뉴

탁월함은 어떻게 나오는가?

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

[Snow-ball]프로그래밍(컴퓨터)/Algorithm

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

Snow-ball 2022. 2. 1. 23:00
반응형

삽입 정렬(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언어 코드 : 

 

배열 정의한 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
 
int main(void) {
    int i, j, temp;
    int arr[10= {11058764329};
    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]);
    }
}
cs

 

값을 입력 받을 수 있는 코드 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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;
}
cs

 

 

 

 

삽입 정렬 알고리즘 특징

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

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

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

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

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

 

 

 

 

 

 

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

나를 꾸미다 - 인테리어소품 베타존

smartstore.naver.com

 

반응형
Comments