단순 삽입 정렬의 특징 살펴보기
다음 배열에서 단순 삽입 정렬을 수행한다고 가정합니다.
2, 3, 4, 5 순서로 선택하여 정렬하나 이미 정렬이 되어 있는 상태이므로 요소를 이동하지 않습니다.
다만 0을 삽입하려면 맨 왼쪽 위치까지 6회에 걸쳐 요소를 이동해야합니다.
| start | 1 | 2 | 3 | 4 | 5 | 0 | 6 |
|---|---|---|---|---|---|---|---|
| 2차 | 1 | 2 | 3 | 4 | 5 | 5 | 6 |
| 3차 | 1 | 2 | 3 | 4 | 4 | 5 | 6 |
| 4차 | 1 | 2 | 3 | 3 | 4 | 5 | 6 |
| 5차 | 1 | 2 | 2 | 3 | 4 | 5 | 6 |
| 6차 | 1 | 1 | 2 | 3 | 4 | 5 | 6 |
| end | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
단순 삽입 정렬은 정렬이 되었거나 그 상태에 가까우면 정렬 속도가 빠르다는 장점이 있지만, 삽입할 곳이 멀리 떨어져 있다면 요소의 이동 횟수가 많다는 단점이 있습니다.
셸 정렬 알아보기
셸 정렬은 단순 삽입 정렬의 장점을 살리고 단점을 보완한 정렬 알고리즘 입니다. 일정한 간격으로 서로 떨어져 있는 두 요소를 그룹으로 묶어 대략 정렬을 수행하고, 간격을 좁혀 그룹의 수를 줄이며 정렬을 반복하여 이동횟수를 줄이는 방법입니다.
다음과 같은 배열을 정리한다고 가정합니다.
먼저 4칸 떨어져 있는 요소를 모아 배열을 4개의 그룹으로 나누고 그룹별로 정렬합니다.
h-정렬
셸 정렬 과정에서 수행하는 각각의 정렬을
h-정렬이라고 합니다. 떨어진 요소를 하나의 그룹으로 묶어 정렬하는 방법이며 4칸 떨어진 요소를 그룹으로 묶으면4-정렬이 됩니다.
| start | 8 | 1 | 4 | 2 | 7 | 6 | 3 | 5 |
|---|---|---|---|---|---|---|---|---|
| 1그룹 정렬전 | 8 | 1 | 4 | 2 | 7 | 6 | 3 | 5 |
| 1그룹 정렬후 | 7 | 1 | 4 | 2 | 8 | 6 | 3 | 5 |
| 2그룹 정렬전 | 7 | 1 | 4 | 2 | 8 | 6 | 3 | 5 |
| 2그룹 정렬후 | 7 | 1 | 4 | 2 | 8 | 6 | 3 | 5 |
| 3그룹 정렬전 | 7 | 1 | 4 | 2 | 8 | 6 | 3 | 5 |
| 3그룹 정렬후 | 7 | 1 | 3 | 2 | 8 | 6 | 4 | 5 |
| 4그룹 정렬전 | 7 | 1 | 3 | 2 | 8 | 6 | 4 | 5 |
| 4그룹 정렬후 | 7 | 1 | 3 | 2 | 8 | 6 | 4 | 5 |
| end | 7 | 1 | 3 | 2 | 8 | 6 | 4 | 5 |
정렬을 마치진 않았지만 정렬을 마친 상태에 가까워 졌습니다.
다음은 4-정렬을 마친 상태에서 2-정렬을 하는 과정입니다.
| start | 7 | 1 | 3 | 2 | 8 | 6 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|
| 1그룹 정렬전 | 7 | 1 | 3 | 2 | 8 | 6 | 4 | 5 |
| 1그룹 정렬후 | 3 | 1 | 4 | 2 | 7 | 6 | 8 | 5 |
| 2그룹 정렬전 | 3 | 1 | 4 | 2 | 7 | 6 | 8 | 5 |
| 2그룹 정렬후 | 3 | 1 | 4 | 2 | 7 | 5 | 8 | 6 |
| end | 3 | 1 | 4 | 2 | 7 | 5 | 8 | 6 |
마찬가지로 정렬을 마치진 않았지만 정렬을 마친 상태에 가까워 졌습니다.
마지막으로 1-정렬까지 마치면 7회의 정렬로 정렬을 마치게 됩니다.
| start | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|
단순 삽입 정렬보다 횟수는 늘지만 전체적으로 요소의 이동 횟수가 줄어 효율적인 정렬이 가능합니다.
다음은 위 내용을 바탕으로 작성한 셸 정렬 프로그램입니다:
//--- 셸 정렬 ---//
static void shellSort(int[] a, int n) {
for (int h = n / 2; h > 0; h /= 2)
for (int i = h; i < n; i++) {
int j;
int tmp = a[i];
for (j = i - h; j >= 0 && a[j] > tmp; j -= h)
a[j + h] = a[j];
a[j + h] = tmp;
}
}증분값(h값) 선택하기
h값이 감소할 때 서로 배수가 되지 않도록 하는 것일 효율 적입니다. 4-정렬로 정렬된 그룹을 2-정렬로 묶는다면 결국 같은 그룹끼리만 정렬되므로 비효율적입니다. 예를 들어 [{1 5}, {2 6}, {3 7}, {4 8}] 그룹으로 묶은 4-정렬을 2-정렬하면 [{1 3 5 7}, {2 4 6 8}] 이 되어 정렬이 된 것들끼리 다시 정렬되기 때문입니다.
다음 수열을 사용하면 효율적입니다. 해당 수열은 1부터 시작하여 3배한 값에 1을 더하는 수열입니다.
다음은 위 내용을 바탕으로 작성한 개선된 셸 정렬 프로그램입니다:
//--- 셸 정렬 ---//
static void shellSort(int[] a, int n) {
int h;
for (h = 1; h < n; h = h * 3 + 1) //초기값 구하기
;
for ( ; h > 0; h /= 3)
for (int i = h; i < n; i++) {
int j;
int tmp = a[i];
for (j = i - h; j >= 0 && a[j] > tmp; j -= h)
a[j + h] = a[j];
a[j + h] = tmp;
}
}셸 정렬의 시간 복잡도는 로 기존의 버블, 선택, 삽입 정렬의 에 비해 매우 빠릅니다. 그리고 멀리 떨어진 요소를 교환하므로 안정적이지 않습니다.