_

1. 소개

삽입 정렬은 \(n\)번의 단계를 통해 원소를 정렬하는데, i번째 단계에서는 i-1번째원소까지 모두 정렬되어 있는 상태에서 1번부터 i번까지 원소들을 정렬한다. 1번부터 i-1번까지 정렬되어 있으니, 그냥 뒤에서부터 훑어보면서 'i'보다 큰 원소들을 만날 때마다 교환해주면 된다.

2. 코드

void Insertion_Sort(){
    for(int i=1; i<=N; i++){
        for(int j=i-1; j>=1; j--){
            if(arr[j+1]>arr[j]){
                break;
            }
            swap(arr[j], arr[j+1]);
        }
    }
}