728x90
소개
- 도널드 쉘(Donald L. Shell)이 고안한 정렬 알고리즘입니다.
- 삽입 정렬의 장점은 살리고, 단점은 보완한 정렬 알고리즘입니다.
- 단순 삽입 정렬
- 장점 : 정렬을 마친 상태에 가까울수록 정렬속도가 높아짐
- 단점 : 삽입할 위치가 멀수록 이동횟수가 증가함
- 정렬할 배열의 요소를 그룹으로 나누어 그룹별 삽입정렬(H-정렬)을 수행합니다.
- 그룹을 합치며 정렬을 반복합니다.
- 증분값 H는 초깃값이 너무 크면 효과가 없습니다.
- n(배열의 요솟수)/9 값을 넘지 않도록 합니다.
- 배열의 요소가 n개 있을 때 시간복잡도는
O(n^1.25)
구현
public class ShellSort {
public void shellSort(int[] arr) {
// 증분값 h
int h;
// h의 초기값을 구합니다.
for (h = 1; h < arr.length / 9; h = h * 3 + 1) {
}
// 정렬을 수행합니다.
for (; h > 0; h /= 3) {
for (int i = h; i < arr.length; i++) {
int j;
int temp = arr[i];
for (j = i - h; j > 0 && arr[j] > temp; j -= h) {
arr[j + h] = arr[j];
}
arr[j + h] = temp;
}
}
}
}
'Problem Solving > 알고리즘' 카테고리의 다른 글
이분 탐색(Binary Search) (0) | 2022.04.23 |
---|---|
퀵 정렬(Quick Sort) (0) | 2021.06.18 |
삽입 정렬(Insertion Sort) (0) | 2021.06.13 |
선택 정렬(Selection Sort) (0) | 2021.06.07 |
버블 정렬(Bubble Sort) (0) | 2021.06.07 |