삽입 정렬 (Insertion Sort)

출처: 위키백과

 

 

 

정의

2번째 원소부터 시작해서 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후,

원소를 뒤로 옮기고 지정된 자리에 값을 삽입하는 정렬 알고리즘이다.

 

선택 정렬 이 원소가 들어갈 자리를 정해두고 해당 자리에 들어올 원소를 찾는 정렬인 것과는 반대로,

삽입 정렬은 원소가 들어갈 자리를 정해두지 않고, 값을 먼저 결정한 다음 해당 값이 들어갈 자리를 앞에서 부터 찾는 알고리즘이다.

즉, 삽입 정렬에서 '삽입'은 값을 특정 자리에 삽입한다는 의미이고, 값이 들어갈 자리를 찾는 알고리즘이라고 생각하면 된다.

 

설명

[5, 4, 3, 2, 1]

위 배열을 오름차순 정렬해보자.

 

2번째 원소인 4부터 시작하여 앞 원소들과 대소 비교를 진행한다.

5는 4보다 큰 값이므로 2번째 자리의 원소를 5로 바꿔준다.

 

[5, 5, 3, 2, 1]

 

더 이상 진행할 원소가 없으므로 대소 비교를 멈추고, 마지막 진행한 자리의 값을 4로 바꿔준다.

 

[4, 5, 3, 2, 1]

 

이번에는 3번째 원소인 3을 기준으로 앞 원소들과 대소 비교를 진행한다.

5는 3보다 큰 값이므로 3번째 자리의 원소를 5로 바꿔준다.

 

[4, 5, 5, 2, 1]

 

같은 방법으로 4와의 비교를 진행 후 값을 바꿔준다.

 

[4, 4, 5, 2, 1]

 

더 이상 진행할 원소가 없으므로 대소 비교를 멈추고, 마지막 진행한 자리의 값을 3으로 바꿔준다.

 

[3, 4, 5, 2, 1]

 

이런 방식으로 나머지 4, 5번째 원소도 정렬을 진행하면 된다.

 

정렬이 진행되는 순서는 아래와 같다.

5, 4, 3, 2, 1
5, 5, 3, 2, 1
4, 5, 3, 2, 1
4, 5, 5, 2, 1
4, 4, 5, 2, 1
3, 4, 5, 2, 1
3, 4, 5, 5, 1
3, 4, 4, 5, 1
3, 3, 4, 5, 1
2, 3, 4, 5, 1
2, 3, 4, 5, 5
2, 3, 4, 4, 5
2, 3, 3, 4, 5
2, 2, 3, 4, 5
1, 2, 3, 4, 5

 

복잡도

 

	시간 복잡도	공간 복잡도
Best	N	N
Worst	N^2	N

 

시간 복잡도는 최상의 경우 바꿔줄 대상을 순회하는 반복(N)만 진행하면 되므로 N이다.

이미 정렬된 배열일 경우 값 비교 과정에서 내부 반복을 진행하지 않고 다음으로 넘어가기 때문이다.

 

오름차순으로 정렬하고자 하는데, 내림차순으로 정렬된 배열일 경우가 최악의 경우이다.

이 경우에는 바꿔줄 대상을 순회하는 반복(N)마다 앞 원소들과 값 비교 및 변경을 진행하는 반복(N)을 진행해야한다.

따라서 O(N^2)이다.

 

공간 복잡도는 Best, Worst 모두 N이다.

매 반복마다 Swap을 통한 메모리 공간을 1회씩 사용하므로 N이다.

 

구현

public class InsertionSort {

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

        print(array);
        sort(array);
        print(array);
    }

    private static void sort(int[] array) {
        int j;
        int temp;

        for (int i = 1; i < array.length; i++) {
            temp = array[i];
            j = i - 1;

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

            array[j + 1] = temp;
        }
    }

    private static void print(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }

        System.out.println("");
    }
}