[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의 앞부분이 항상 정렬되어 있음을 알 수 있다
(이미지 출처 : https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif)
시간복잡도
-
Best-case의 경우
- 이미 배열이 모두 정렬되어 있는 경우 배열을 순회만 하면 되기 때문에 시간복잡도는 \(O(N)\)
-
input 케이스의 양이 적고, 이미 정렬되어 있다면 고려해볼만은 하다
-
Worst-case의 경우
- 모든 경우의 수마다 swap을 하며 위치를 바꾼다면 1+2+3+ … + (n-1) 번의 작업을 수행해야 하므로
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