삽입 정렬, Insertion Sorting 에 대하여

 

우리가 가장 먼저 정렬을 배울 때 배우는

삽입정렬. 그것에 대해서 알아보자

 

---

 

입력으로는 n 개의 수열이 주어지고

출력은 n개의 수열들이 정렬된 채로 나오기를 원한다.

아래와 같이 하는 것이 삽입 정렬을 적용하는 방법이다.

 

 

위와 같은 방식은 어떤 식으로 구현해야 할까??

 

우선 pseudo code로 봐보자

 

조금만 프로그래밍 공부를 했다면 프로그램이 어떻게 작동하는 지는 알 것이다.

하지만 이를 추상화시켜서 설명하는 것은 어려울 수 있다.

 

다시 말하면 삽입 정렬의 코드를 보여줄 수는 있지만

삽입 정렬이 뭐냐고 물어보면 정확하게 답하기 어려운 이유가 그렇다.

 

그렇다면 한 줄씩 뜯어서 살펴보자.

 

첫 번째

2번째 원소부터 n번째 원소까지 끝까지 조사를 한다.

 

두 번째

조사를 하는 해당 원소는 key가 된다.

 

세 번째

해당 조사하는 원소의 앞 원소에 대해서 조사한다.

 

네 번째 - 1

해당 앞 원소가 존재하고 해당 앞 원소가 key 값보다 크다면

지금 해당하는 앞 원소를 조사하는 원소의 위치를 뒤로 당겨서 배열에 넣는다.

그리고 다음 원소를 조사한다. (해당 조사하는 원소의 앞 원소)

 

네 번째 - 2

해당 앞 원소가 존재하지 않거나 해당 앞 원소가 key 값보다 작다면

즉, 맨 앞의 원소를 조사하고 있거나 조사하는 해당 앞 원소가 key 보다 작거나 같으면

해당 앞의 위치는 올바른 위치이다. 해당 key 값은 해당 앞 원소의 뒤에, 즉, 해당 위치에 온다.

 

다시 코드로 바꿔보겠다.

조사하는 원소와 정렬할 원소의 구분을 잘 해보자

#include<iostream>

using namespace std;



int arr[6] = [5,2,4,6,1,3];


void intsertion_sort(int *p){
	for(int j = 2; j<=6; j++){ #0
    
    	key = arr[j]; #1
        
        int i = j - 1; #2
        
        while(i>0 || arr[i] > key){ #3
        	arr[i+1] = arr[i]; #4
        	i = i - 1; #5
        }
        arr[i+1] = arr[i]; #6
    }

}

int main(){




	return  0 ;
}

 

#0 맨 앞에 올 원소를 정하기 위해 2부터 시작함

 

#1 정렬할 원소를 key에 저장함

 

#2 해당 앞의 원소에 대해서 조사함

 

#3~5는 한묶음임

#3 해당 앞의 원소 정렬할 원소보다 크다면 혹은 맨 앞의 원소를 가리킨다면

#4 해당 원소는 정렬할 원소보다 뒤로 가야하므로 1칸 뒤로 보냄..

#5 뒤로 보냈으니 조사하던 위치의 앞의 원소를 조사함

 

#6 #3의 반대 즉, 조사하는 원소보다 정렬할 원소가 더 커진다면 

조사하는 원소의 뒤에 정렬할 원소가 들어가야함.

 

---

 

2번부터 조사하니까

의미가 있다.

즉, 앞에가 정렬되어 있다는 가정하에 이 알고리즘을 돌리는 것이다.

Incremental 방식의 이유라 불리는 것도 이것이다.

 

즉, j번째 루프를 돌고 있다면 j-1번째 까지는 정렬되어 있는 상태를 의미한다.

 

---

 

요약하자면

2번째 원소부터 조사한다.

앞의 원소와 비교하면서 자신의 들어갈 자리를 찾는다.

해당 자리는 나보다 조사하는 원소가 작아지면 그 뒤에 들어가면 된다.

 

이 알고리즘은 n번째 원소의 자리를 찾을 때는

n-1 번째까지는 이미 정렬이 되어있기 때문에 가능한 방법이다.

 

---

 

번외로 내림차순으로 정리하려면 어떻게 해야할까?

 

똑같이 2 번째 부터 시작하되

조사할 원소가 정렬하려는 값보다 커야하겠지?즉, 조사하는 원소가 정렬하려는 값보다 작다면 뒤로 땡겨서 한칸을 만들어주고조사하는 원소가 더 커버리면 땡겨진 한 칸에 정렬하려는 원소를 집어넣으면 되겠다.

 

---

 

다시 번외로..

Recursive로 구현할 수 있을까??

그렇다.아까도 말했듯이 n-1번째 까지 정렬되어 있으니 n번째도 해당된다고 했다.작은 문제로 쪼개기가 가능하다는 것이다.

 

즉, 마지막 값을 찾으면된다.n의 위치에 n개의 원소 중 가장 큰 값을 넣으려고 한다.n-1의 위치에 n-1개의 원소 중 가장 큰 값을 넣으려고 한다.....하면 된다.