- 손 안의 카드를 정렬하는 방법과 유사하다.
- 새로운 카드를 기존의 정렬된 카드 사이에 올바른 자리를 찾아 삽입한다.
- 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
- 최선의 경우, O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될만큼 좋은 정렬 알고리즘이다.
- 정렬은 2번째 위치(index)의 값을 standard에 저장한다
- standard와 이전에 있는 원소들과 비교하여 자리를 바꾸며 삽입해 나간다.
- 1번으로 돌아가서 다음 위치(index)의 값을 standard에 저장하고 이 과정을 반복한다.
private static void sort(int[] arr) {
for (int i = 1; i < arr.length; i++) { // 1
int standard = arr[i];
int index = i - 1;
while ((0 <= index) && standard < arr[index]) {//2
arr[index + 1] = arr[index];
index--;
}
arr[index + 1] = standard; // 3
print(arr, i);
}
}
private static void print(int[] arr, int step) {
System.out.print(step + "단계 : ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// 단계별 결과.
1단계 : 6 7 2 4 3 9 1
2단계 : 2 6 7 4 3 9 1
3단계 : 2 4 6 7 3 9 1
4단계 : 2 3 4 6 7 9 1
5단계 : 2 3 4 6 7 9 1
6단계 : 1 2 3 4 6 7 9
- 첫 번째 원소 앞(왼쪽)에는 원소가 없기 때문에 두 번째 위치(index)부터 탐색을 시작한다. standard에 임시로 기준 위치(index) 값을 저장하고, index에는 기준 위치(standard) 이전의 위치(index)를 저장한다.
- 이전 위치를 가리키는 index는 음수가 되지 않고, 이전 위치의 값이 1번에서 선택한 기준 위치의 값보다 크다면 오른쪽으로 한 칸씩 이동시켜준다. 그리고 index가 더 이전 위치를 가리키도록 한다.
- 2번에서 반복문이 끝나고 난 뒤, index에는 standard가 들어갈 위치의 인덱스-1의 위치를 가리키게 된다. 2번의 반복문에서 standard보다 큰 값들의 위치를 한 칸씩 오른쪽으로 밀었기 때문이다. 따라서 (index+1) 위치에 standard가 들어갈 위치이기 때문에, 삽입해준다.
- 최악의 경우(역으로 정렬되어 있을 경우), 선택 정렬과 마찬가지로 (n-1)+(n-2)+ ... +2+1 => n(n-1)/2 즉, O(N^2)이다.
- 하지만, 모두 정렬이 되어 있는 경우, 한번씩만 비교하므로 O(N)의 시간 복잡도를 가지게 된다. 또한, 이미 정렬되어 있는배열에 자료를 하나씩 삽입/제거하는 경우에는 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문이다.
- 최선의 경우 : O(N)
- 평균과 최악의 경우 : O(N^2)
- 주어진 배열 안에서 교환을 통해 정렬이 이루어지기 때문에 O(N)이다.
- 알고리즘이 단순하다.
- 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있다.
- 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.
- 선택 정렬이나 버블 정렬에 비하여 상대적으로 빠르다.
- 비교적 많은 수들의 이동을 포함한다.
- 비교할 수가 많고 크기가 클 경우에 적합하지 않다.(배열의 길이가 길어질수록 비효율적)
- 평균과 최악의 시간 복잡도가 O(N^2)이므로 비효율적이다.