삽입 정렬(insertion sort)은 손안의 카드를 정렬하는 방법과 유사하다. 우리는 카드 게임을 할 때, 새로운 카드가 들어오면 새로운 카드가 들어오면 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입함으로써 정렬이 유지되게 한다.
삽입 정렬은 처음에 2번 째 위치의 값을 key로 정해서 시작한다. key 값을 자신의 왼쪽에 놓인 것들과 하나씩 비교하면서 자신의 위치를 찾으면 그 자리의 있는 것과 자리를 바꾸게 된다. 자바로 삽입 정렬을 구현해보자.
public class Sort {
public static void main(String[] args) {
int[] list = {5, 3, 2, 1, 10, 11, 9};
int i = 0, j = 0, key = 0;
for (i = 1; i < list.length; ++i) {
key = list[i];
for (j = i - 1; j >= 0 && key > list[j]; --j) {
list[j + 1] = list[j];
}
list[j + 1] = key;
}
System.out.println(Arrays.toString(list));
}
}
삽입 정렬의 복잡도는 입력 자료의 구성에 따라서 달라진다. 최선의 경우는 먼저 입력자료가 이미 정렬되어 있는 경우는 가장 빠르다. 최악의 경우는 입력 자료가 역순일 경우이다.
삽입 정렬의 외부 루프는 n-1번 실행되고 각 단계에서 1번의 비교와 2번의 이동만 이루어지므로 총 비교횟수는 n-1번, 총 이동횟수는 2(n-1)번이 되어 알고리즘 시간 복잡도는 O(n)이다. (최선의 경우이기 때문에 그렇다)
각 단계에서 앞에 놓인 자료들은 전부 한 칸씩 뒤로 이동하여야 한다. 따라서 외부 루프안의 각 반복마다 i번의 비교가 수행되므로 총 비교횟수는 다음과 같다.
1 + 2 + ... + (n-1) = n(n-1)/2 = O(n*n)
역순이라고 생각하면 정렬을 하는 과정에서 계속 자신의 위치보다 하나 앞에 있는 것과 비교1번, 이동1번 씩을 수행해서 자신의 위치 까지 와야한다. (그것이 i번이다)
총 이동횟수는 외부 루프의 각 단계마다 i+2번의 이동이 이루어지므로 다음과 같다.
i번의 경우는 위의 비교처럼 n-1번 반복문을 수행하면 O(n*n)이 되고, +2번의 경우는 2(n-1)을 해서 두개를 더하면 된다.
시그마의 경우를 생각하자. 따라서 O(nn)이다. (n(n-1)/2 + 2(n-1) = (nn + 3n -4)/2) 가 정확하다.
- 안정한 정렬 방법으로서 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하다.
- 대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.
- 레코드의 양이 많고 레코드 크기가 클 경우에 적합하지 않다.
- 비교적 많은 레코드들의 이동을 포함한다.