[알고리즘 개념] 삽입 정렬 (insertion sort) c++

삽입정렬

 

삽입정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여
자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

 

+ 손 안의 카드를 정렬하는 방법과 같다.
새로운 카드를 정렬된 카드 사이의 알맞은 사이를 찾아 삽입해준다.

 

두번째 원소부터 시작하여 그 앞 원소들과 비교하여 삽입할 위치를 지정하고 원소를 뒤로 옮기고
그 자리에 원소를 삽입하여 정렬한다.

 

 

삽입정렬 GIF

 

출처 : https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

 

이런식으로 두번째 원소부터 마지막 원소까지 정렬된 앞 원소들과 비교하여 알맞은 위치를 찾아 삽입한다.

역시 gif가 이해가 잘된다...

 

 

C++로 구현

 

#include<iostream>
using namespace std;
int a[10] = { 3,6,7,1,4,2,9,0,5,8 };

void insertion_sort(int a[])
{
	int key, j, i;
	for (i = 1; i < 10; i++) {  // 1
		key = a[i];
		for (j = i - 1; j >= 0 && a[j] > key; j--) {  // 2
			a[j + 1] = a[j];
		}
		a[j + 1] = key; //3
	}

}


int main()
{
	insertion_sort(a);

	for (int i = 0; i < 10; i++) {
		cout << a[i] << " ";
	}
	return 0;
}

 

1.  i = 1 부터 시작한다. (즉 두번째 원소부터!!) --> 정렬 시켜줄 원소의 index
2.  이미 정렬된 앞 원소들을 뒤에서부터 앞으로 거꾸로 비교해가며 정렬시킨다. 정렬 시켜줄 원소 (key)가 이미 정렬된 앞 원소와 비교하여 key 보다 정렬된 값이 크면 j 번째를 j + 1번째로 이동시킨다.
3.  2번의 for 문이 조건이 안맞으면 for문을 벗어나므로 a[j+1] 번째에 key값을 저장시켜준다. 여기서 j + 1이라는걸 유의하자!!!

 

 

 

알고리즘 설명

 

2를 정렬하려고 할때 설명

 

5를 정렬하려고 할때 설명

•  5를 정렬하려고 한다. a[4] = key 가 된다.
• 앞 원소들 3, 4, 8, 9 는 이미 정렬된 상태이다.
•  i는 4이므로 j = 3부터 시작한다.  a[3] 는 key값보다 크므로 뒤로 원소를 이동시켜준다.
• j = 2 일때도 a[2] 가 key값보다 크다는 조건과 j가 양수인 조건을 만족하므로 뒤로 원소를 이동시켜주고 i를 1 감소시킨다.
• j = 1 일때는  조건에 맞지 않기 때문에 for문을 빠져나오게 된다.
• j = 1 이였기 때문에 a[2] = key 즉 a[2] 에 5를 저장해주면 된다.