[JAVA] 삽입정렬(Insertion Sort) 개념과 코드 구현

삽입정렬(Insertion Sort)은 배열의 각 요소를 자기보다 앞쪽에 위치한 정렬된 배열과 비교하여 올바른 위치에 삽입하는 알고리즘이다.

배열이 길어질수록 효율이 떨어지지만 구현이 간단하다는 장점이 있다.

비교정렬이며 안정 정렬이다.

구분	최악 시간복잡도	최선 시간복잡도	평균 시간복잡도	공간복잡도(메모리)	안정성
삽입정렬	O(N^2)	O(N)	O(N^2)	1	Y

 

알고리즘

1. 요소를 하나씩 순회하면서 알맞은 곳에 삽입하는 형태로 정렬을 수행한다.

2. 마지막 요소까지 검토가 완료되면 전체 정렬이 완료된다.

소스코드

public static int[] insertionSort(int[] arr) {

    // 배열에서 요소를 순회하면서 자기보다 앞에 있는 배열(앞부분은 정렬이 완료되어있음)에서 알맞은 위치에 넣어준다.
    // 인덱스 0번은 비교대상 없으므로 인덱스 1번부터 시작한다.
    for (int i = 1; i < arr.length; i++) {

        // 비교할 대상(타겟)을 추출한다.
        int target = arr[i];

        // 만약 현재 위치보다 앞부분에 타겟보다 큰값이 있다면, 그 값 앞에 타겟을 넣어준다.
        // 위 그림에서 예로 들면 현재 다섯번째에 있는 1은 6-> 5-> 3-> 2-> 와 크기를 비교한 뒤 맨 앞에 위치하게된다. 
        // 현재 위치보다 앞부분은 정렬되어있으므로 뒤에서부터 i-- 하면서 값을 찾아간다.
        while (i >= 1 && arr[i - 1] > target) {
            arr[i] = arr[i - 1];
            arr[i - 1] = target;
            i--;
        }
    }
    return arr;
}