삽입 정렬(Insertion Sort)

배열의 모든 요소를 앞에서부터 이미 정렬된 배열과 비교하여 적절한 위치를 찾는 정렬 방법이다.

#include <iostream>
using namespace std;

int main() {
	int tmp, arr[10] = {10,5,4,6,2,3,7,9,1,8};
	for(int i = 0; i < 9; i++) {
		int j = i;
		while(arr[j] > arr[j + 1]) {
			tmp = arr[j];
			arr[j] = arr[j + 1];
			arr[j + 1] = tmp;
			j--;
		}
	}
	for(int i = 0; i < 10; i++)
		cout << arr[i] << " ";
}

최악의 경우

번의 비교를 하게 되므로, O(n^2) 가 된다.


역시나 선택정렬이나 버블정렬과 같은 시간복잡도를 가지지만 실제론 삽입정렬이 가장 빠르다.
필요할 때만 위치를 바꾸기 때문에 거의 정렬이 된 상태일 때 가장 빠르고, 자원을 덜 사용하여 효율적으로 작동한다.
때문에 다른 정렬 알고리즘의 일부로 사용되는 경우가 있다.

algorithm	average	worst	best	space
insert	O(N^2)	O(N^2)	O(N)	O(1)