[C++] 정렬 - 삽입 정렬(Insertion Sort)

- 자료 배열의 모든 값을 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입해서 정렬을 완성한다.

- best case에서 (배열의 크기 - 1)만큼만 정렬하고자 탐색하고 바로 끝나고, stability하다.

#include <iostream>
using namespace std;

void Print(int* arr, int size)
{
	for (int i = 0; i < size; i++)
		cout << arr[i] << ' ';
	cout << '\n';
}

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

	int arr[] = { 4,3,2,10,12,1,5,6 };
	int n = sizeof(arr) / sizeof(arr[0]);

	for (int i = 0; i < n - 1; i++)
	{
		if (arr[i] > arr[i + 1])
		{
			int insertNum = arr[i + 1];
			int insertIndex = 0;
			for (int k = i; k >= 0 && insertNum < arr[k]; k--)
			{
				arr[k + 1] = arr[k];
				insertIndex = k;
			}
			arr[insertIndex] = insertNum;
			Print(arr, n);
		}
	}
	cout << '\n';
	Print(arr, n);

	return 0;
}