[알고리즘] 삽입 정렬(Insertion Sort)

다음 숫자들을 오름차순으로 정렬하시오.
2, 4, 5, 1, 3

---

앞의 선택 정렬과 버블 정렬은 시간 복잡도 O(N²)을 가지는 정렬 알고리즘이었다. 그렇다면 삽입 정렬의 시간 복잡도는 어떻게 될까?

 

우선, 삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 방법으로 동작한다. 선택 정렬, 버블 정렬은 무조건 위치를 바꾸는 방식이었다면, 삽입 정렬은 필요할 때만 위치를 바꾸게 된다.

 

그럼 앞선 정렬 방식보다 효율적일까? 정답은 NO!

 

삽입 정렬은 기본적으로 '정렬이 되어있다고 가정'을 한다는 점에서 특정한 경우에 따라 굉장히 빠른 속도를 낼 수 있다. 하지만 반복문이 두 번 들어가있기 때문에 최악의 경우 시간 복잡도가 O(N²)이 될 수 있다.

 

그림으로 살펴보자!

처음 두 수 2, 5는 2가 더 앞에 있으므로 정렬하지 않는다.

 

다음 두 수 5, 4는 5가 더 앞서 있으므로, 맨 앞까지 확인하면서 자리를 바꾼다.

 

5와 4를 바꾸고 그 앞의 2, 4를 확인한다.

 

그 다음, 5와 1을 확인하고 5가 더 앞서 있으므로, 맨 앞까지 확인하면서 자리를 바꾼다.

 

마지막으로 5, 3의 자리를 시작으로 맨 앞까지 확인하면 바꿔주면 정렬을 완료할 수 있다.

 

코드로 나타내면 다음과 같다.

 

public class Main {

    public static void main(String[] args) {
        int[] arr = {2, 5, 4, 1, 3};

        for(int i=0; i<4; i++) {
            int j = i;

            while(j >= 0 && arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                j--;
            }
        }

        for(int i=0; i<5; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

 

삽입 정렬은 자리를 바꾸지 않아도 될 때는 바로 넘어간다. 하지만 위와 같이 정렬이 되어있지 않은 상황에서는 앞선 정렬들과 마찬가지로 전부 확인하기 때문에 수행 시간이 늘어날 수밖에 없다.

 

그래서 앞선 정렬 방식과 삽입 정렬의 시간 복잡도는 동일하다.

삽입 정렬의 시간 복잡도는 O(N²)이다.