삽입 정렬의 장점을 살리고, 단점을 보안한 정렬 알고리즘
삽입 정렬은 버블 정렬과 선택 정렬과 비교 했을 때 좀더 낫다.
(모두 탐색 안함, 단 최악일 때는 동일)
근데 타켓의 삽입되어야 할 위치가 현재 위치에서 멀리 떨어진 곳이라면, 많은 이동을 해야 한다.
이를 보안하기 위해 간격을 두고, 부분 리스트로 삽입 정렬을 시행해 점점 줄어가며 이동 거리를 좁히는 것이다. (즉 애초에 멀리 떨어진 숫자들은 빠르게 제자리로 찾아간다.)
시간 복잡도는 O(N의 1.25승) 정도라고 한다.
(1.25 승이면 대체 얼마인거지)
정렬 방법
1. 간격(gap)을 설정한다.
2. 각 간격별로 분류 된 서브(부분) 리스트에 대해 삽입정렬을 한다.
3. 각 서브(부분) 리스트의 정렬이 끝나면 간격을 줄인다.
4. 간격이 1이 될 때 까지 2번 과정으로 되돌아가며 반복한다.자바로 구현하면 다음과 같다.
static void shell_sort(int[] arr) {
// 간격을 반절씩 좁힌다.
for (int h = arr.length/2; h > 0; h /= 2) {
// 여기서 헷갈릴 수 있는데 부분리스트를 하나씩 비교하는 것이다.
// 삽입 정렬을 시행
for (int i = h; i < arr.length; i++) {
int prev = (i - h);
int target = arr[i];
// 여기도 헷갈리기 쉽다. 간격 만큼 옮겨 줘야 한다.
while(prev >= 0 && arr[prev] > target) {
arr[prev + h] = arr[prev];
prev -= h;
}
// 루프에서 빠져나온 경우,
// prev 값은 삽입되어야 할 위치보다 한 간격 앞에 있으므로
arr[prev + h] = target;
}
}
}참조한 책 및 사이트
https://gmlwjd9405.github.io/2018/05/08/algorithm-shell-sort.html