삽입 정렬(insertion sort) in C++

1. 삽입 정렬을 이용한 오름차순

#include <iostream>

using namespace std;

int a[101], n, flag;
int main() {
	freopen("input.txt", "rt", stdin);
	cin >> n;
	for(int i=0; i<n; i++) {
		cin >> a[i];
	}
	
	for(int i=1; i<n; i++) {
		int temp = a[i];		// 삽입될 원소 
		for(int j=i-1; j>=0; j--) {
			flag = j;
			if(a[j] > temp) a[j+1] = a[j];		// 뒤로 미는 부분
			else break; 
		}
		a[flag]=temp;		// 삽입 
	}
	
	for(int i=0; i<n; i++) {
		cout << a[i] << " ";
	}
	
	return 0;
}

오름 차순 내림 차순 정렬의 기준에 따라, 0번째 원소가 아닌 1번째 원소부터 자신보다 아래 수의 위치하는 원소들의 자리와 비교하여, 기준에 따라 각 원소들의 자리를 하나씩 뒤로 미루고 해당 원소를 삽입한다.

• 시간 복잡도 : n^2
  ex)
  5
  13 5 11 7 23