3. 삽입 정렬 (Insertion Sort)

 

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int N = 5;
	int arr[5] = { 1, 2, 3, 4, 0 };

	for (int i = 1; i < N; i++) { //삽입 정렬
		for (int j = i - 1; j >= 0; j--) {
			if (arr[j] > arr[j + 1]) swap(arr[j], arr[j+1]); //키 값인 arr[j+1] 보다 왼쪽 값이 더 크면 교환한다
			else break; //키 값이 더 클 경우 더 비교할 필요 없으므로 종료시킨다
		}
	}

	for (int i = 0; i < N; i++) cout << arr[i] << "\n";
    
    return 0;
}