이번 시간에는 저번 시간에 이어 기본 정렬 중 하나인 삽입 정렬(Insertion sort)에 대해서 알아보도록 하겠습니다.



삽입 정렬(Insertion sort) - 안정 정렬(Stable sort)


삽입 정렬이란 정렬된 구간그렇지 않은 구간 둘로 나누고, 


정렬되지 않은 구간의 맨 앞 원소를 가져와 정렬된 구간에 삽입하는 알고리즘입니다.


알고리즘의 수행 단계는 다음과 같습니다.


1) 주어진 데이터 중 맨 앞의 원소를 정렬된 구간으로 설정하고, 나머지를 그렇지 않은 구간으로 정합니다.


2) 삽입 데이터 정하기 : 정렬되지 않은 구간의 맨 앞 데이터를 삽입 데이터(key 값)로 정한다.


3) 삽입 위치 파악하며 데이터 밀어내기 : 정렬 구간을 역순으로 탐색하며 Key 값이 삽입될 위치를 파악합니다.


4) 모든 데이터가 정렬될 때까지 2-3 과정을 반복합니다.


좀 더 자세하게 그림으로 보여드리겠습니다.





이 그림을 위에서 언급한 순서와 함께 설명하자면 다음과 같습니다.


1) 주어진 데이터(7-3-2-1-5) 에서 7을 정렬된 구간으로 설정하고 나미저 3-2-1-5를 정렬되지 않은 구간으로 설정하여 시작합니다.


1 회전 : 

2) 3을 정렬된 구간에 삽입하기 위해 Key 값으로 정합니다.

3) 정렬된 구간을 7부터 역순으로 탐색하며 삽입 위치를 합니다. 이때, (Key 값 > 비교 데이터) && (더 이상 비교할 데이터가 없는가?)를 만족해야 합니다. 따라서, 조건을 비교해가며 결국 첫 번째 자리에 삽입되게 됩니다.


2 회전 :

2) 2를 정렬된 구간에 삽입하기 위해 Key 값으로 정합니다.

3) 1회전때와 마찬가지로 조건을 비교해 가며 결국 첫 번째 자리에 삽입되게 됩니다.


3 회전 :

2) 1을 정렬된 구간에 삽입하기 위해 Key 값으로 정합니다.

3) 1, 2회전때와 마찬가지로 조건을 비교해 가며 결국 첫 번째 자리에 삽입되게 됩니다.


4 회전 :

2) 5를 정렬된 구간에 삽입하기 위해 Key 값으로 정합니다.

3) 1, 2, 3회전과 달리 두 번째 비교작업때 Key 값이 비교데이터(3) 보다 크므로 조건에 위배됩니다. 따라서, 그때 빈 공간에 삽입되게 됩니다.



소스 코드


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 <iostream>
 
using namespace std;
 
int main()
{
    int a[5= {7,3,2,5,1};
    int key,j;
 
    //삽입 정렬
    for(int i = 1 ; i< 5; i++){
        key = a[i];
        j = i;
        while(key < a[j-1&& j>0){
            a[j] = a[j-1];
            j--;
        }
        a[j] = key;
    }
 
    //출력
    for(int i = 0 ; i< 5; i++)
        cout << a[i] << " ";
 
    return 0;
}
 
cs



배열 a : 정렬하고자 하는 데이터


key : 정렬되지 않은 구간에서 정렬 구간으로 옮기며 정렬할 값


j : key 값의 삽입 위치


Line 11: 

i 는 정렬되지 않은 구간에서 삽입할 데이터의 위치를 의미합니다. 

따라서 첫 번째 값을 정렬 구간으로 설정하기 때문에 1부터 시작합니다.


Line 12 :

정렬할 데이터를 Key 변수에 저장합니다.


Line 14 :

Key < a[j-1] -> Key 값 보다 큰 값이 이전에 있으면 계속 진행하는 조건 입니다.

j>0 -> key 값이 제일 작아 처음에 삽입되어야 하는 조건입니다.


Line 15-16 :

데이터의 삽입을 위해 정렬된 구간의 데이터들을 뒤로 한칸씩 미룹니다. 또한 다음 탐색을 위해 j값을 감소시킵니다.


Line 18 :

한 회전을 통해서 삽입할 위치를 찾았으니 데이터를 삽입합니다.



시간 복잡도


삽입 정렬에서 최악의 경우는 버블 정렬과 마친 가지로 역순으로 정렬되어 있을 경우다.


즉, 매 회전마다 삽입되는 데이터가 정렬 구간의 처음에 삽입된다면,


1회전에 1번, 2회전 2번 ... n-1 회전에 n-1번 동작하기 때문에


1부터 n-1 까지 등차 수열의 합이므로 n에 대한 2차식이다. 따라서 시간복잡도는 이 됩니다.



 

+ Recent posts