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

안녕하세요. BlockDMask 입니다.

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

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

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

0. 원리

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

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

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

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

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

  

  

1. 코드 및 결과

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

#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] = {9, 5, 3, 7, 1};
    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;
}
 
 
 

> 결과

2. 시간 복잡도

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

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