[알고리즘] - 삽입 정렬 (Insertion-sort)

1. 삽입 정렬(Insertion Sort)이란?

선택한 원소를 현재 정렬된 배열 범위 내의 적절한 위치에 삽입하는 방법이다.

구현하기 쉬운 알고리즘이지만, 시간 복잡도는 O(n²) 으로 다른 정렬 알고리즘들에 비해서 느린 편에 속한다. 

---

2. 삽입 정렬의 수행 방식

삽입 정렬 과정

① 현재 index의 원소를 선택한다.

② 정렬된 부분 내에서, 현재 선택한 원소가 들어갈 적절한 삽입 위치를 찾는다. 

③ 삽입 위치부터 끝까지 데이터를 한 칸씩 뒤로 민다.

④ 삽입 위치에 현재 선택한 원소를 삽입한다.

⑤ index를 1 증가시키고, 다시 ①부터 반복한다. (index가 배열의 크기만큼 커질때까지 반복)

 

 

다시 말해, 인덱스를 증가시켜 가면서 배열의 원소를 선택하고, 선택한 원소를 정렬된 범위 내의 적절한 위치에 삽입하는 방식으로 진행된다. 

 

끝까지 정렬을 수행하면 위와 같다.

 

 

 

---

3. 삽입 정렬 구현 (C++)

#include <iostream>
using namespace std;

//삽입 정렬 함수(여기서 n은 배열의 크기)
void insertion_sort(int arr[], int n) {

	for (int i = 1; i < n; i++) {

		//현재 인덱스가 가리키는 원소값
		int current = arr[i];

		//정렬된 부분의 가장 오른쪽 원소부터 왼쪽 방향으로 탐색
		int j = i - 1;
		while (j >= 0 && arr[j] > current) {
			arr[j + 1] = arr[j];	//자리 한칸씩 이동
			j--;
		}
		arr[j + 1] = current;
	}
}


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

	int list[10] = { 3,9,10,2,5,6,4,8,1,7 };

	cout << "정렬 전" << "\n";
	for (int i = 0; i < 10; i++) {
		cout << list[i] << " ";
	}

	insertion_sort(list, 10);

	cout << "\n\n정렬 후" << "\n";
	for (int i = 0; i < 10; i++) {
		cout << list[i] << " ";
	}
}

실행 결과 정상적으로 삽입 정렬이 수행된 것을 확인할 수 있다.