킹의 개발일지
삽입 정렬 본문
삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 방법으로 문제를 해결한다.
버블, 선택 정렬들이 비교후 무조건 위치를 바꾸는 형식이었다면 삽입 정렬은 필요할 때만 위치를 바꾼다.
삽입 정렬은 앞에 있는 원소들이 이미 정렬 됐다고 가정한다. 이런 가정 때문에 버블, 선택 정렬들 보다 효율적이다.
삽입 정렬 방식을 살펴 보도록 하자.
1 10 5 8 7 6 4 3 2 9
특정 인덱스에서, 해당 원소가 어디로 들어가면 되는지 찾으면 된다.
1) 1의 경우 제일 앞에 있으므로 들어갈 자리가 없기 때문에 그대로 둔다.
2) 10의 경우 1의 앞과 뒤에 위치할 수 있다. (밑줄 친 곳이 10이 들어갈 수 있는 위치이다.)
_ 1_ 10 5 8 7 6 4 3 2 9
이때 10은 1보다 크기 때문에 1의 앞에 위치할 수 없다. 따라서 1의 뒤에 위치해야한다.
1 5 10 8 7 6 4 3 2 9
3) 8의 경우 총 네군데 위치할 수 있다.
_ 1 _ 5 _ 10 _ 8 7 6 4 3 2 9
이때 8은 5보다는 크고 10보다는 작기 때문에 5뒤에 위치한다.
1 5 8 10 7 6 4 3 2 9
3) 7 의 경우 총 다섯 군데 위치할 수 있다.
_ 1 _ 5 _ 10 _ 8 _ 7 6 4 3 2 9
이때 7은 5보다는 크고 8보다는 작기 때문에 5뒤에 위치한다.
1 5 7 8 10 6 4 3 2 9
...
원소를 특정 인덱스에 삽입하는 과정을 계속하면 정렬이 완료된다.
삽입정렬은 특정 인덱스에 있는 원소가 들어갈 자리를 확인하고 삽입시킨다. 삽입 시키는것도 정렬된 배열 모두를 순회하지 않고 그 자리까지 필요한 만큼만 이동시킨다.
특정 인덱스 앞에있는 원소들은 이미 정렬이 완료된 상태이다. 삽입 정렬은 이미 정렬이 끝난 원소는 연산하지 않기 때문에 O(N^2)의 시간복잡도를 갖는 다른 정렬 알고리즘들과 비교했을 때 효율적이다.
/**
* O(N^2)
* 거의 정렬이 이루어진 배열에는 엄청 빨리 연산이 처리된다.
*/
public class 삽입정렬 {
public static void main(String[] args) {
int i, j, temp;
int[] arr = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
for (i = 0; i < 9; i++) {
j = i;
while (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
j--;
}
}
for (int e : arr) {
System.out.print(e + " ");
}
}
}
while 절에서 조건을 계속 확인해서 딱 필요한 만큼만 이동 할 수 있게 해주는 것이다.
삽입 정렬은 특정한 경우에 굉장히 빠르게 정렬을 수행한다.
삽입 정렬은 필요한 만큼만 이동을 하기 때문에 이미 정렬이 어느정도 끝난 배열은 이동 횟수가 적어져 연산횟수가 낮아진다.
2 3 4 5 6 7 8 9 10 1
2, 3, 4, 5, 6, 7, 8, 9, 10까지 비교연산만 수행함으로 굉장히 빠르게 처리된다. 그리고 맨 뒤에 있는 1에만 한 자리씩 옮겨가며 위치를 찾아간다.
때문에 어느정도 정렬이 된 배열에 한해서 매우 빠른 연산을 할 수 있는 알고리즘이다.