Insertion Sort(삽입정렬)

기본 아이디어: 현재 비교하고자 하는 target원소와 이전의 원소들을 삽입할 위치를 정한 후 나머지 원소를 오른쪽으로 옮기고 그 자리에 target원소를 삽입하는 방식이다. 삽입정렬은 안정정렬이다.

작동방식
1. 2번째 원소부터 비교를 시작한다.
2. target원소 왼쪽에 있는 원소들과 비교하여 자신보다 값이 큰 원소가 나오면 순서에 맞게 삽입하고 나머지 원소를 오른쪽으로 이동시킨다.
3. 정렬이 될때까지 반복

시간복잡도: O(n^2)

java 코드

static int[] insertionSort(int[] arr, int size) {

        for (int i = 1; i < size; i++) {
            int idx = i;
            for (int j = i - 1; j >= 0; j--) {
                if (arr[idx] < arr[j]) {
                    int tmp = arr[idx];
                    arr[idx] = arr[j];
                    arr[j] = tmp;
                    --idx;
                }
            }
        }

        return arr;
    }

코드에 오류가 있으면 말씀해주세요.