정렬 알고리즘 - 삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)

 

삽입 정렬 이란?

 

 - 이미 정렬되어 있는 것에 하나씩 추가해 정렬하는 방법

 

 - 대상이 이미 정렬되어 있다면 매우 빠른 속도로 동작한다.

 

 - N개의 데이터가 주어졌을 때 O($N^2$)의 시간복잡도를 가진다. 

 

---

삽입 정렬 예시

1. 초기 상태(첫 번째 원소는 정렬 완료)

2. 이미 정렬된 범위(1)에 현재 위치(2번째)의 값을 넣어 정렬. 

3. 이미 정렬된 범위(1~2)에 현재 위치(3번째)의 값을 넣어 정렬.

4. 이미 정렬된 범위(1~3)에 현재 위치(4번째)의 값을 넣어 정렬.

5. 이미 정렬된 범위(1~4)에 현재 위치(5번째)의 값을 넣어 정렬.

6. 이미 정렬된 범위(1~5)에 현재 위치(6번째)의 값을 넣어 정렬.

 

7. 정렬 완료

 

---

 

삽입 정렬 코드(C++)

#include <iostream>
#include <vector>

using namespace std;

void insertionSort(vector<int> &vec)
{
	int i, j, data;
	for (i = 1; i < vec.size(); i++)
	{
		data = vec[i];
		for (j = i - 1; j >= 0; j--)
		{
			if (vec[j] > data)
			{
				vec[j + 1] = vec[j];
			}
			else
				break;
		}
		vec[j + 1] = data;
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> vec{ 7,1,8,3,5,2};

	cout << "정렬 전 : ";
	for (auto i : vec)
		cout << i << ", ";
	cout << endl;

	insertionSort(vec);

	cout << "정렬 후 : ";
	for (auto i : vec)
		cout << i << ", ";
	cout << endl;
	
	return 0;
}

 

 

실행 결과