삽입정렬이란
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하여 정렬을 완성하는 알고리즘
방법
- 처음 key값은 두번째 자료부터 시작하여, key값 앞의 자료들 중에 맞는 위치에 삽입한다.
삽입정렬의 특징
장점
- 안정된 정렬 방법
- 레코드 수가 적을 경우 알고리즘 자체가 매우 간단하여 다른 복잡한 정렬방법보다 유리할 수도 있다.
- 대부분의 레코드가 이미 정렬되어 있는 경우 매우 효율적이다.
단점
- 비교적 많은 레코드들이 이동해야한다.
- 레코드 수가 많고 레코드 크기가 클 경우 적합하지 않다.
삽입정렬의 시간복잡도
최선의 경우 : 정렬이 되어 있는 경우
- 이동 없이 1번의 비교만 이루어져 (n-1)번만 돈다
- O(n)
최악의 경우 : 정렬이 역순으로 되어 있는 경우
- 각 반복마다 i번의 비교를 해야 한다 -> 루프를 n(n-1)/2번 돈다
- O(n^2)
평균 시간복잡도
- O(n^2)
구현코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class InsertionSortEx {
public static void insertion_sort(int[] a) {
insertionSort(a, a.length);
}
public static void insertionSort(int[] a, int size) {
for (int i = 1; i < size; i++) {
int target = a[i];
int j = i-1;
// 타겟이 이전 원소보다 크기 전까지 반복하기
while(j >= 0 && target < a[j]) {
// 이전 원소를 한 칸씩 뒤로 미룬다
a[j+1] = a[j];
j--;
}
// 반복문에서 탈출시 앞의 원소들이 타겟보다 작다
a[j+1] = target;
}
}
}
reference
[알고리즘] 삽입 정렬(insertion sort)이란 자바 [JAVA] - 삽입 정렬 (Insertion Sort)+
