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

 

목차

삽입 정렬이란?

삽입 정렬이란 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신이 들어갈 위치를 찾아 삽입함으로써 정렬을 하는 알고리즘이다. 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.

 

삽입 정렬의 원리는 두 번째 자료부터 시작해서 그 앞의 정렬되어 있는 자료들과 비교하여 삽입할 위치를 찾은 뒤에 자료를 뒤에 옮기고 지정한 자료를 삽입하여 정렬하는 알고리즘이다.

즉, 2번째 자료는 1번째 자료, 3번째 자료는 2번째와 1번째 자료, 4번째 자료는 3번째, 2번째, 1번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다.

이제 예시를 한번 보겠다.

 

 

 

소스 코드

 

static void insertionSort() {
    int j, temp;
    int n; //배열 크기
    int[] array = new int[n];  //정렬할 배열
    for (int i = 0; i < n-1; i++) {
        j = i;  //현재 정렬할 숫자 (Key)

        while (j >= 0 && array[j] > array[j+1]) {
            //왼쪽에 있는 값이 더 클 경우 서로 교환해준다
            temp = array[j];
            array[j] = array[j + 1];
            array[j + 1] = temp;
            j--;
        }
    }

    //정렬한 배열 출력
    for (int i = 0; i < n; i++) {
        System.out.print(array[i] + " ");
    }
}

 

 

삽입 정렬 시간 복잡도

시간 복잡도는 최상의 경우, 최악의 경우로 나눠서 설명해보겠다.

 

1. Best Case (배열이 이미 정렬된 경우)

 

비교 횟수

• 이미 정렬되어 있으므로 이동은 없으며 1번의 비교만 이루어짐
• 비교 횟수 : (n - 1) 번

시간 복잡도 : O(n)

 

2. Worst Case (배열이 역순으로 정렬된 경우)

 

비교 횟수

• 각 반복마다 i번의 비교 수행
• 횟수 : (n - 1) + (n - 2) + … + 2 + 1 = n(n - 1) / 2

 

교환 횟수

• 외부 loop의 각 반복마다 (i + 2) 번의 이동 발생
• n (n - 1)/2 + 2(n - 1) = (n^2 + 3n - 4) / 2

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

 

 

삽입 정렬의 장단점

장점

• 구현이 쉽다
• 배열이 거의 정렬되어 있으면 O(n)의 시간 복잡도를 가진다
• 버블 정렬, 선택 정렬보다 보통 더 효율적이다

 

단점

• 배열의 있는 많은 요소들을 정렬해야 하면 많은 요소를 옮겨야 한다
• 자료의 수가 많고 자료의 크기가 클 경우에는 적합하지 않다