행복했던 휴가를 마치고 다시 현생으로 돌아왔다.
이번 주는 업무로 매우 바쁠 예정이기에 평일이 되기 전에 게시글을 하나라도 올리려고 한다.
앞에서 다룬 단순 삽입 정렬의 단점을 보완한 셸 정렬에 대해 알아볼 것이다.
셸 정렬(shell sort)
단순 삽입 정렬의 특성
- 정렬을 마친 상태에 가까울 수록 정렬 속도가 빨라진다. (장점)
- 삽입할 위치가 멀리 떨어져 있으면 이동해야하는 횟수가 많아진다. (단점)
여기서 단순 삽입 정렬의 장점은 살리고 단점을 보완한 알고리즘이 셸 정렬(shell sort)이다.
쉽게 말해 멀리 떨어져있어도 이동하는 거리를 줄이는 방법이다.
여러 개의 그룹으로 나누어 정렬함으로써 이 거리를 어떻게 줄일 수 있다.
셸 정렬의 예시 (4-정렬 -> 2-정렬 -> 1-정렬)
8개의 요소가 있는 배열에서 4칸만큼 떨어진 요소끼리 먼저 정렬한다.
7 4 2 8 1 3 5 6
7과 1의 자리를 바꾸고, 4와 3의 자리를 바꾸는 식으로 말이다.
이때 이를 '4-정렬'이라고 하는데 4-정렬을 마치면 아래와 같은 상태가 된다.
1 3 2 6 7 4 5 8
이러한 방법을 반복하며 2-정렬, 1-정렬식으로 점차 정렬된 상태에 가까워지면서 1-정렬을 적용하면 정렬을 마치게 된다.
1 2 3 4 5 6 7 8
이 방법을 통해 7칸을 당겨야하는 최악의 경우의 수가 사라지듯이 요소 이동의 횟수가 줄어들어 효율적인 정렬이 가능하게 된다.
증분값의 선택
최악의 경우의 시간복잡도는 O(n^2) 이며, 수행 속도는 간격에 따라 좌우된다.
이 간격을 증분값이라고 부르는데 h-정렬에서 h값을 뜻한다.
가장 유명한 히바드(Hibbard) 간격을 사용하면 O(n^(1.5)) 라고 한다.
히바드 간격은 증분값의 간격을 2^k - 1로 두고 k를 1씩 줄여서 2^k -1, ... , 15, 7, 3, 1로 간격을 설정하는 방법이다.이 후 많은 실험을 통한 현재까지의 셸 정렬의 최적의 시간복잡도는 O(n^(1.25)) 으로 알려지고 있다.
간격 설정에 따른 차이는 그룹의 섞임 차이에 의해 나타난다.
4-정렬과 2-정렬에서 4칸만큼 떨어진 요소들 끼리 아래와 같이 비교를 한다.
7 1 4 3 2 5 8 6
7 1
4 3
2 5
8 6그리고 비교로 움직인 요소들은 아래와 같다.
1 3 2 6 7 4 5 8
1 7
3 4
2 5
8 6여기서 2-정렬을 진행하면 비교 요소는 아래와 같다.
1 2 7 5
3 6 4 8근데 살펴보면 4-정렬에서 비교한 값들이 한 그룹에 다시 뭉쳐 또 비교를 해야하는 모습을 볼 수 있다.
이처럼 증분값을 서로 안 겹치게 설정하는 방법이 더욱 효율적인 알고리즘을 만들게 해준다.
요소가 충분히 섞이도록 1부터 시작하여 3배를 곱하고 1을 더하는 수열을 간격으로 설정하여 효율적인 알고리즘을 제작해볼 것이다.
void shell(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 tmp = a[i];
int j;
for (j = i - h; j >= 0 && a[j] > tmp; j -= h) {
a[j + h] = a[j];
}
a[j + h] = tmp;
}
}
}단순 삽입 정렬에서 사용한 조건을 응용하였고, 처음에 반복문을 활용해 n을 넘지않는 가장 큰 h값을 구하였다.
for문을 초기화 없이 사용해본 적은 처음이었는데, 불필요한 변수를 굳이 선언할 필요가 없어져 더 좋았다.
다음 글에서는 가장 빠른 정렬 알고리즘 중 하나로 널리 사용되는 퀵 정렬에 대해 알아보겠다.
