<개인공부>/[Algorithm]

삽입정렬 (Insertion Sort) 이론과 코드

사용자 BlockDMask 2017. 8. 5. 23:30
반응형

안녕하세요. BlockDMask 입니다.


오늘은 간단한 정렬 알고리즘 중에 삽입 정렬 (Insertion Sort) 에 대해서 알아보겠습니다.


이상한 곳이 있으면, 댓글로 말해주시기 바라겠습니다.

댓글을 보고 고치도록하겠습니다.
따끔한 지적 부탁드리겠습니다.


0. 원리

  • Insertion Sort 는 말 그대로 '삽입' 꽂아 넣는 정렬입니다.

  • 자신보다 앞의 원소가 큰지 작은지 비교를 하여서 자신의 위치를 찾아서 '삽입' 하는 정렬입니다.

  • 앞의 원소를 비교해야 하기 때문에 arr[1]~arr[n] 까지 진행합니다. (두번째 원소인 arr[1] 부터 시작.)

  • 삽입을 하면 데이터가 하나씩 밀려야 하기 때문에 배열이 길어질수록 효율이 떨어집니다.

  • 그림을 통해서 과정을 살펴 보겠습니다. (오름차순을 기본으로 하겠습니다)


1. 코드 및 결과


T) C/C++ 로 구현한 코드


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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<stdio.h>
 
#define MAX_LEN 5
 
 
void InsertionSort(int * arr){
    int i, j;
    int key;
 
    for(i=1; i< MAX_LEN; i++){
        key = arr[i];
        
        for(j=i-1; j>=0; j--){
        
            if(arr[j] > key){       //key의 앞자리를 하나씩 보면서 비교
                arr[j+1= arr[j];  //앞자리 값이 key값보다 크다면 하나씩 이동
            }else{                  //key보다 작은 값이 나오면 break;
                break;
            }
        
        }
        
        arr[j+1= key;             //그 자리에 key값을 넣는다.
    }
}
 
int main(void){
    int arr[MAX_LEN] = {95371};
    int i;
    
    for(i=0; i<MAX_LEN; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
 
 
    InsertionSort(arr);
 
    for(i=0; i<MAX_LEN; i++){
        printf("%d ", arr[i]);
    }
 
    return 0;
}
 
 
 
cs


> 결과


2. 시간 복잡도

  • 이중 for문 내부의 조건문 if가 n * n-1 번 일어나므로 시간복잡도 빅오는    입니다.


다음시간에는 선택 정렬 (Selection Sort)에 대해서 포스팅 하겠습니다.

반응형