Insertion Sort(삽입 정렬)

삽입정렬은 각 숫자를 적절한 위치에 삽입하는 형식으로 문제를 풀게 된다. 그래서 맨 앞부터 정렬이 시작되게 된다.

삽입정렬의 시간복잡도도 n개의 목록을 두번 거치기에 Big-O는 O(N^2)이 되게 된다.

Insertion Sort Code

#include<iostream>

int main()
{
	int a[] = {5, 8, 2, 7, 4, 1, 9, 6, 3};
	int temp, i, j;
	
	for(i = 0 ; i < 8 ; i++)
	{
		j = i;
		while( j >= 0 && a[j] > a[j + 1])
		{
			temp = a[j];
			a[j] = a[j + 1];
			a[j + 1] = temp;
			j--;
		}
	}
	
	for(i = 0 ; i < 9 ; i++)
		std::cout << a[i] << " ";
	return 0;
}

이미지 출처
도움 자료