삽입 정렬 (Insertion Sort)
1. 개념 설명
(1) 삽입 정렬은 인덱스 0번 위치 원소부터 시작하여 뒤 원소들과 비교하고 삽입할 위치를 지정한 후,
원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하는 알고리즘이다.
(2) 삽입 정렬은 선택 정렬과 유사하지만, 좀 더 효율적인 알고리즘이다.
(3) 선택 정렬과 함께 인간에게 뭔가를 정렬하라고 하면 무의식적으로 사용하는 대표적인 알고리즘이다.
2. 과정
- 실제로 수행되는 과정이며, 삽입하는 동시에 정렬한다.
3. 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public class InsertSort {
public static void main(String[] args) {
int[] A = { 7, 2, 8, 10, 1 };
for(int i=1; i<A.length; i++) {
int tmp = A[i];
int prev = i-1;
while((prev>=0)&&(tmp<A[prev])) {
A[prev+1] = A[prev];
prev--;
}
A[prev+1] = tmp;
}
System.out.println(Arrays.toString(A));
}
}
|
cs |
4. 시간 복잡도
(1) 만약 모두 정렬되어 있는 최선의 경우는 한 번씩 밖에 비교를 하지 않으므로 O(n)의 시간복잡도를 가진다.
(2) 또한 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는 최고의 알고리즘으로 꼽힌다.
( 탐색을 제외한 오버헤드가 적기 때문이다. )
(3) 그러나, 만약 역으로 정렬되어 있는 최악의 경우는 수행 횟수를 보면
(n-1) + (n-2) + ... + 2 + 1 --> n(n-1)/2가 나오게 되므로, O(n²)의 시간복잡도를 가진다.
5. 공간 복잡도
(1) 주어진 배열 안에서 정렬이 일어나므로, 공간 복잡도는 O(n)이다.
6. 장점
(1) 코드가 매우 단순하며 직관적이다.
(2) 대부분의 원소들이 정렬되어 있는 경우라면, 매우 효율적이다.
(3) 주어진 배열 안에서 정렬되기 때문에 다른 메모리 공간이 필요하지 않다.
( 제자리 정렬 (in-place sorting) )
(4) 안정 정렬이다.
(5) 거품 정렬, 선택 정렬과 같은 O(n²) 알고리즘보다는 상대적으로 빠르다.
7. 단점
(1) 평균과 최악의 시간 복잡도가 O(n²)이므로, 비효율적이다.
(2) 거품 정렬과 선택 정렬과 같이 배열의 길이가 길어질수록 비효율적이다.