36. 삽입정렬 (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★☆☆☆☆

#include <stdio.h>
#include <vector>

using namespace std;

int main()
{
	int n;
	scanf("%d", &n);
	
	vector<int> num(n, 0);
	
	for(int i = 0; i < num.size(); i++)
		scanf("%d", &num[i]);
		
		
	int temp = 0;
	for(int i = 1; i < num.size(); i++)
	{
		for(int j = i-1; j >= 0; j--)
		{
			if(num[j] > num[j+1])
			{
				temp = num[j];
				num[j] = num[j+1];
				num[j+1] = temp;
			}
		}
	}
	
	for(int i = 0; i < num.size(); i++)
		printf("%d ", num[i]);
		
	return 0;
}

1. 삽입정렬 : 2번째 원소(target)부터 왼쪽 원소와 비교하면서 target이 더 작다면 그 원소와 위치를 스왑하는 정렬방식

- 선택 · 버블정렬 (O(N^2)) 알고리즘보다 빠르고 안정적인 정렬이다. ( 배열이 길어질수록 효율은 떨어진다. )

- 추가 공간이 필요없다.

- 데이터를 비교하면서 찾아가기 때문에 비교정렬이다.