[알고리즘] Insert sort

오름차순 정렬 코드 예시

void insert_sort(int* arr, int N) {
    for(int i=1; i<N; i++) { //index 1부터 시작해야함.
        int k=i; int v = arr[k];
        //이중포문 대신에 간단한 while문
        while(k) {
            if(v<arr[k-1]) { //선택값과 아랫값들을 차례로 비교
                arr[k] = arr[k-1]; //밀어넣기
                k--;
            } else
                break;
        }
        // 최종적으로 k-1 인덱스에 넣는 것이 목적이므로, 밀어넣기 후 k--해서 넘겨온 값을 그대로 이용하는 것.
        if(k!=i) //위치변경이 있었을 경우에만 실행
            arr[k]=v;
    }
}

1번째 인덱스부터 시작해서 이전 인덱스를 차례로 검사하여, 해당 인덱스보다 값이 큰 것들을 한칸씩 뒤로 밀어넣은 후에 앞 빈자리에 해당 인덱스의 값을 다시 넣는 것을 반복.