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

Input: n개 수들의 수열 (a1, a2, ..., an)

Output: a’1 <= a'2 <= ... <= a'n을 만족하는 입력 수열의 순열 (재배치)

 

정렬하고자 하는 숫자를 키라고 한다.

 

삽입 정렬 알고리즘은 크기가 작은 정렬에 효율적이다. 삽입 정렬은 손에 쥔 카드를 정렬하는 것과 방법이 같다. 테이블에서 카드를 한 장 가져와 적절한 위치에 삽입한다. 적절한 위치를 찾기 위해 이미 들고 있는 카드와 새 카드를 오른쪽에서 왼쪽으로 비교한다. 손에 들고 있는 카드는 항상 정렬되어 있다.

 

출처) https://upload.wikimedia.org/wikipedia/commons/e/ea/Insertion_sort_001.PNG

 

의사코드)

for j = 2 to A.length
	key = A[j]
    // A[j]를 정렬된 배열 A[1...j - 1]에 삽입
    i = j - 1
    while i > 0 and A[i] > key
    	A[j + 1] = A[i]
        i = i - 1
    A[i + 1] = key

입력은 정렬하려는 n개의 수열이 들어있는 배열 A[1...n]이다. 인덱스 j는 카드를 쥔 손으로 가져가 정렬할 현재 카드를 나타낸다. 부분 배열 A[1...j - 1]은 현재 손에 쥔 정렬된 카드고 나머지 부분 배열 A[j + 1...n]은 아직 탁자에 쌓여 있는 카드다.

 

루프 불변성을 확인해보자.

(루프불변성 참고) 2024.04.12 - [프로그래밍 공부] - [알고리즘] 루프 불변성

초기조건: 루프의 첫 반복이 시작되기 전, 즉 j = 2일 때 루프 불변성이 성립하는지 살펴본다. 이때 부분배열 A[1...j - 1]은 A[1] 하나의 원소로 구성되고 그 부분배열은 정렬되어 있으므로 루프의 첫 반복시작 전에 루프 불변성이 성립한다.

유지조건: 매 반복 시 루프 불변성이 유지되는지 살펴본다. for의 바디 부분은 A[j]의 올바른 위치를 찾을 때까지 A[j - 1], A[j - 2], A[j - 3], ...을 오른쪽으로 한 자리씩 이동시키는 작업을 하고 A[j]값을 적절한 위치에 삽입한다. 그러면 배열 A[1 ... j]는 기존 루프 A[1 ... j]와 동일한 원소를 정렬한 상태로 갖게 된다. j가 1씩 증가하면서 다음 반복에서도 루프 불변성이 유지된다. 

종료조건: 루프가 종료되었을 때 어떤 상황이 발생하는지 확인한다. for루프는 j가 A.length = n보다 커질 때, 즉 j = n + 1일 때 종료된다. 앞의 루프 불변성 기술에서 j에 n + 1을 넣어보면 부분 배열 A[1..n]은 원래 A[1..n]의 원소로 구성되면서 정렬된 순서로 저장된다. A[1..n]은 전체 배열이므로 배열 전체가 정렬되었으며 따라서 알고리즘은 타당하다.

 

728x90

 

자바 예제 코드)

import java.util.Arrays;

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

        for (int j = 1; j < arr.length; j++) {
            int key = arr[j];
            int i = j - 1;
            while (i >= 0 && arr[i] > key) {
                arr[i + 1] = arr[i];
                i--;
            }
            arr[i + 1] = key;
        }

        System.out.println(Arrays.toString(arr));
    }
}

출력: [1, 2, 3, 4, 5, 6]