[Algorithm] Insertion Sort

Insertion Sort

삽입정렬

Stable sort vs Unstable sort

Stable sort (안정 정렬) : 정렬 후에도 원래의 순서를 유지한다
Unstable sort (불안정 정렬) : 정렬 후 원래의 순서가 유지된다는 보장이 없다

원리

배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 구간과 비교하여 삽입한다. 단계별로 나눠본다면

원소를 선택한다. (초기값은 두 번째 인덱스부터 시작한다)
내가 선택한 원소를 temp에 저장한다
배열을 거슬러 올라가며 temp값 보다 작은 값이 나올 때까지 비교를 해 나간다
비교를 하는 과정에서 temp와 비교하는 원소들의 index가 1칸씩 이동하게 된다
작은 값이 나오면 비교를 멈추고 작은 값 바로 뒤의 index에 temp를 삽입한다
내가 선택한 원소의 다음값을 선택한다
배열의 마지막 원소까지 1에서 4를 반복한다

텍스트로 쓴 위 과정을 애니메이션으로 표현한다면 다음과 같다. 선택된 key 값을 기준으로 key의 앞부분이 항상 정렬되어 있음을 알 수 있다

insertion sort

(이미지 출처 : https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif)

시간복잡도

Best-case의 경우
- 이미 배열이 모두 정렬되어 있는 경우 배열을 순회만 하면 되기 때문에 시간복잡도는 $O(N)$
input 케이스의 양이 적고, 이미 정렬되어 있다면 고려해볼만은 하다
Worst-case의 경우
- 모든 경우의 수마다 swap을 하며 위치를 바꾼다면 1+2+3+ … + (n-1) 번의 작업을 수행해야 하므로
$\dfrac {n(n-1)}{2} = O(N^2)$

JAVA 구현 코드

void InsertionSort(int[] arr) {
    
	// 배열의 모든 요소를 순차적으로 순회한다
    for(int index=1; index<arr.length; index++) {
    	// 현재 인덱스의 값을 임시 변수에 복사한다
        int temp = arr[index];
        int beforeIndex = index - 1;
        
        while ((beforeIndex >= 0) && (arr[beforeIndex] > temp)) {
            arr[beforeIndex+1] = arr[beforeIndex];
            arr--;
        }
        
        arr[beforeIndex + 1] = temp;
    }	
        
}

Date: May 26, 2019

Tags: Algorithm