Insertion_sort.cpp

#include<iostream>

// Print all elemets in array
void print(int A[], int N)
{
	for (int i = 0; i < N; i++) {
		if (i != 0)
			std::cout << " ";
		std::cout << A[i];
	}
	std::cout << std::endl;
}

// Insertion sort
void insertion(int A[], int N)
{
	for (int i = 1; i < N; i++) {
		// Value to insert
		int v = A[i];

		int j = i - 1;
		while (j >= 0 && A[j] > v) {
			A[j + 1] = A[j];
			j--;
		}
		A[j+1] = v;
		print(A, N);
	}
}

// MAIN FUNCTION
int main()
{
	// Input
	int n;
	int A[1000];
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		std::cin >> A[i];
	}

	print(A, n);
	// Insertion sort
	insertion(A, n);
	return 0;
}