[C++] 삽입정렬

• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교합니다.
• 자신의 위치를 찾아 삽입하는 방식으로, 선택돤 arr[i] (temp)가 arr[j]보다 작을경우, 배열을 옆으로 밀어서 옮깁니다.
• 0에 도달하거나, temp보다 큰 값이 나온다면, 더 이상 진행하지 않고 해당 위치에 temp를 삽입합니다.

 

#include <iostream>
#include <vector>

int main()
{
	int N;
	scanf_s("%d", &N);

	std::vector<int> arr(N);

	for (int i = 0; i < N; ++i)
		scanf_s("%d", &arr[i]);

	int i, j;

	for (i = 1; i < N; ++i)
	{
		int temp = arr[i];

		for (j = i; j > 0; --j)
			if (arr[j - 1] > temp)
				arr[j] = arr[j - 1];
			else
				break;

		arr[j] = temp;
	}

	for (int i = 0; i < N; ++i)
		printf("%d ", arr[i]);
}