[알고리즘] 삽입정렬 (Insertion Sort) C++

0. 목차

 

1. 삽입정렬의 개념
2. 삽입정렬의 과정 정리
3. 삽입정렬의 시간복잡도
4. 삽입정렬 코드

---

1. 삽입정렬의 개념

 

정렬의 개념은 앞의 선택정렬에서 설명한것과 동일하다. (khu98.tistory.com/102?category=858723)

선택정렬에서 정렬을 하는법은, 정렬될 자리에 들어갈 원소를 선택한뒤, 교환을 하며 정렬을 하는거였다면, 

삽입정렬은 해당 원소가 자기가 들어가야할 자리에 찾아가 삽입하며 정렬을 하는 방법이다.

 

 

선택정렬의 예와 동일한 예를 사용해보자.

 

배열에 5 1 4 7 2 가 있고, 이것을 오름차순으로 정렬하고싶다고 해보자. 편의상 인덱스를 1부터 시작한다고 가정하자.

이때, 맨 앞에있는 1번인덱스를 정렬되어있는 원소라고 생각한다.

	인덱스	1	2	3	4	5
	데이터	5	1	4	7	2

 

 

 

이제 2번인덱스에 있는 데이터인 1을 자기자리를 찾아 삽입시킬것이다.

오름차순 정렬이므로 5보다 앞에있어야 하므로 5와 1을 SWAP해준다.

STEP 1 RESULT	인덱스	1	2	3	4	5
	데이터	1	5	4	7	2

1과 5가 자기자리를 잘 찾았다.

 

 

 

다음으로 정렬되지않은 데이터중 3번인덱스에 있는 4의자리를 찾아줄것이다.

먼저 4의 앞에있는 5와 비교를 해보자. 4는 5보다 작으니 5보다 앞에 있어야 하므로 swap을 해주자.

STEP 2	인덱스	1	2	3	4	5
	데이터	1	4	5	7	2

그런뒤, 1과 비교를 했을때 , 4는 1보다 크니 1 뒤에 있는것이 맞다. 따라서 4가 있어야하는 위치에 잘 삽입이 된것이다.

STEP 2 RESULT	인덱스	1	2	3	4	5
	데이터	1	4	5	7	2

1 4 5 가 자기자리를 잘 찾았다.

 

 

 

다음으로 4번인덱스에 있는 7의 자리를 찾아주자. 앞에 정렬된 배열의 맨 뒤의 원소인 5와 비교를 해보았을때, 7이 더 크므로 바꿔주지 않아도 된다. 

이때 5 앞에있는 원소들과는 비교를 안해도되는가???

이에 대한 답변은 앞에는 이미 정렬되어있는 배열이므로 자기보다 작은 원소를 만나면, 그 앞은 다 자신보다 작은 데이터라는 확신을 할 수 있으므로, 그 자리가 알맞은 자리라고 확신을 할 수 있게되는것이다.

STEP 3 RESULT	인덱스	1	2	3	4	5
	데이터	1	4	5	7	2

 

 

 

마지막으로 5번 인덱스에있는 2를 위치를 찾아 삽입시켜줄것이다.

먼저 정렬되어있는 제일 마지막 원소인 7과 비교해본다.

2가 7보다 작으니, 7보다 앞으로 가야하므로 2와 7을 SWAP해준다.

STEP 4-1	인덱스	1	2	3	4	5
	데이터	1	4	5	2	7

 

다음으론 2와 5를 비교해준다. 2가 5보다 작으므로 더 앞에있어야한다. 2와 5를 SWAP해주자.

STEP 4-2	인덱스	1	2	3	4	5
	데이터	1	4	2	5	7

 

다음으론 2와 4를 비교해준다. 2가 4보다 작으므로 더 앞에있어야 한다. 2와 4를 SWAP해주자.

STEP 4-3	인덱스	1	2	3	4	5
	데이터	1	2	4	5	7

 

다음으론 2와 1을 비교해준다. 2가 1보다 크므로, 2는 1의 뒤에 있어야 한다. 따라서 2의 자리를 찾은것이다.

STEP 4 RESULT	인덱스	1	2	3	4	5
	데이터	1	2	4	5	7

 

 

이렇게 5 1 4 7 2 의 원소가 모두 자기자리를 찾아 삽입되어 정렬되었다.

---

2.삽입정렬 과정 정리

 

1. 먼저 맨 앞의 원소를 정렬된 원소라고 정한다.
2. 정렬되지 않은 데이터들중 맨 앞에있는 원소를 선택한다.
3. 정렬된 원소들을 맨 뒤에서부터 탐색한다.
4. 자신의 앞에있는 원소가 자신보다 크다면, SWAP을 한뒤, 계속 탐색한다.
5. 자신보다 작은원소를 만났다면 멈추고 2번으로 돌아간다.
6. 마지막 원소까지 모두 2~5번 과정을 거친다.

---

3.삽입정렬 시간복잡도

 

N개의 데이터를 정렬한다고 한다면,

최악의 상황은 2번에서 선택한 원소가 매번 최솟값이라 정렬된 배열의 맨 앞까지 탐색을 하는경우이다. 따라서 맨 앞까지 탐색하는 시간 O(N)이 걸리는 로직을 N-1개의 원소가 반복해야하므로, 시간복잡도는 O(N2)이 된다.

---

4.삽입정렬 코드

 

#include<iostream>
using namespace std;

int main() {
	int arr[5] = { 5,1,4,7,2 };
	int size = 5;
	int temp;

	cout << "정렬 전 :\t";
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << " ";
	}
	cout << "\n";

	for (int i = 1; i < size ; i++) {
		for (int j = i ; j >= 1; j--) {
			if (arr[j - 1] > arr[j]) {
				int temp = arr[j - 1];
				arr[j - 1] = arr[j];
				arr[j] = temp;
			}
			//자기자리를 찾았으면, 더이상 탐색할 필요 x
			else {
				break;
			}
		}

		//중간결과
		cout << i + 1 << "번째 결과 :\t";
		for (int j = 0; j < 5; j++) {
			cout << arr[j] << " ";
		}
		cout << "\n";
	}

	cout << "정렬 결과:\t";
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << " ";
	}
	cout << "\n";

	return 0;
}