삽입 정렬

왼쪽은 정렬된 숫자들 오른쪽은 비정렬 숫자들

오른쪽에서 숫자들을 확인하고 왼쪽의 알맞은 자리에 해당 숫자를 삽입한다.

삽입 정렬= 삽입한다! 무엇을? 한개씩 순차적으로 고른 숫자(오른쪽에서)

 

#include <iostream>
using namespace std;

int main() {
    int arr_len;
    cin >> arr_len;
    int arr[arr_len];
    int j;
    for(int k=0; k<arr_len;k++) {
        cin >> arr[k];
    }
    for(int i=1; i<arr_len;i++){
        int tmp = arr[i];
        for(j=i-1; j>=0; j--){
            if(arr[j]>tmp) arr[j+1] = arr[j];
            else break;
        }
        arr[j+1] = tmp;
    }

    for(int i=0; i<arr_len ; i++) {
        cout << arr[i] << " " ;
    }
}

i=1에서부터

why?

j가 탐색해야 하기 때문이다

j는 i보다 작고 만약 i번째 수보다 j번째 수가 크면 알맞게 삽입하고 그 반대의 경우면 가만히 있는다.

이 아이디어에서 기반

 

-a[ j ]가 tmp( i 번째 숫자(j<i))보다 크면 안되기 때문에

a[j+1] = a[j]로 바꾼다.

이 반복문을 수행하고 가장 마지막으로 바뀐 자리에 tmp를 삽입한다.