삽입 정렬(Insertion Sort)은 배열의 구간을 정한다음 원소를 비교하며 정렬을 하는 방식입니다.
1. 0 번째 인덱스의 원소와 1 번째 인덱스의 원소를 비교 합니다. (ex. 범위는 0-1 인덱스)
2. 1 번째 원소가 0 번째 원소보다 작으면 첫 번째 원소의 인덱스는 1 증가하고 두 번째 원소의 인덱스는 1 감소합니다.
3. 이런식으로 범위가 1씩 증가하며 원소를 비교한 뒤 큰 숫자의 인덱스를 1씩 늘려주고 작은 숫자의 인덱스를 숫자 만큼 감소 해주세요.
아래는 위의 순서에 맞게 실행한 예제입니다.
- 배열에 저장되는 값은 [3, 6, 0, 9, 1] 입니다.
| Sequence | Array | Arrange |
| 1 | [3, 6, 0, 9, 1] | 변화 없음 |
| 2 | [3, 6, 0, 9, 1] | 0(a[2] -> a[0]) 3(a[0] -> a[1]) 6(a[1] -> a[2]) |
| 3 | [0, 3, 6, 9, 1] | 1(a[4] -> a[1]) 3(a[1] -> a[2]) 6(a[2] -> a[3]) 8(a[3] -> a[4]) |
아래는 삽입 정렬을 구현한 자바 예제입니다.
package algorithm;
import java.util.Arrays;
public class InsertionSort {
public static void main(String[] args) {
int[] a = { 3, 6, 0, 9, 1 };
int[] sorted_a = insertionSort(a);
System.out.println(Arrays.toString(sorted_a));
}
public static int[] insertionSort(int[] a) {
int i, j;
for (i = 0; i < a.length; i++) {
int temp = a[i];
int range = i-1;
while (range >= 0 && a[range] > temp) {
a[range+1] = a[range];
range--;
}
a[range+1] = temp;
}
return a;
}
}