삽입 정렬

삽입정렬 역시 시간복잡도는 O(N*N)을 가진다.

삽입정렬은 각 숫자를 적절한 위치에 삽입하는 방법으로 해결한다. 다른 정렬은 무조건 위치를 바꾸는 방식이었다면 삽입정렬은 필요할 때만 위치를 바꾸게 된다.

이에 따라서 버블 정렬과 선택정렬과 같은 시간복잡도를 가지고 있지만 좀 더 효율적이다.

for (int i = 0; i < 9; i++) {
        j = i;
        while (array[j] > array[j + 1]) {
            temp = array[j];
            array[j] = array[j + 1];
            array[j + 1] = temp;
            j--;
        }
    }

현재 값이 우측에 있는 값보다 클 경우에 좌측으로 이동시킨다
좌측값은 정렬되어있다고 생각하고 있기때문에 어느정도 정렬이 완료된 수열을 정렬할때 굉장히 효율적이다.