셸 정렬(Shell sort)

이번 포스팅은 삽입 정렬(Insertion sort)의 단점을 보완 하기 위해 

고안 된 정렬 방법 인 셸 정렬(Shell sort)에 대해 알아 보겠습니다.

셸 정렬(Shell sort)은 삽입 정렬(Insertion sort)의 단점인 레코드를 적합한 위치에 삽입하는 과정에서

레코드들을 뒤로 옮기는 연산은 줄이기 위해, 특정한 거리씩 떨어진 레코드들끼리 삽입 정렬을 하고,

그 거기를 차츰 줄여나가면서 최종적으로는 전체 레코들에 대해 삽입 정렬을 하는 정렬 방법이다.

위 그림을 보면 어느 정도 이해가 될 것이다.

과정을 간단하게 설명하자면

1. 레코드를 십수 개 정도 듬성듬성 나누어서 삽입 정렬한다.

2. 레코드를 다시 잘게 나누어서 삽입 정렿나다.

3. 이러한 방법을 반복하여 모든 레코드들이 정렬 될 때까지 반복한다.

이 때 레코드를 몇 개로 분할 하는 가에 따라 전체적인 성능에 결정적인 영향을 미친다.

셸 정렬을 처음 고안한 Donald Shell은 초기에 간격을 (k는 0 이상의 자연수) 혹은 으로 잡았다.

추후 Marcin Ciura의 연구에 의하면 1, 4, 10, 23, 57, 132, 301, .... 과 같은 간격을

사용하는 것이 연산 시간을 많이 줄인다고 증명하였다.

h를 간격이라 할 때, 평균적인 공식은

h(1) = 1

h(i+1) = 3h(i) + 1

로 하면 좋은 결과를 얻을 수 있으며, 이 순열은 1, 4, 13, 40, 121, ...의 역순으로 된 순열이다.

만약 레코드의 크기가 150일 때 먼저 121개의 부분 리스트로 나누어 삽입 정렬을 이용하고,

또 다시 40개의 부분 리스트로 나누어 삽입 정렬을 이용한다.

이러한 과정을 반복 한 후 마지막으로 간격이 1일 때(리스트 전체) 삽입 정렬로 끝낸다.

 

셸 정렬의 소스 코드이다.

셸 정렬을 분석하면 삽입 정렬에 비하여 2가지의 장점이 있다.

- 연속적이지 않은 부분 리스트에서 레코드의 교환이 일어나면 더 큰 거리를 이동한다.

반면 삽입 정렬에서는 한 번에 한 칸씩만 이동된다. 

따라서 교환되는 요소들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 높아진다.

- 부분 리스트는 어느 정도 정렬이 된 상태이기 때문에 부분 리스트의 개수가 1이 되게 되면

셸 정렬은 기본적으로 삽입 정렬을 수행하는 것이지만 더욱 빠르게 수행 된다.

이것은 삽입 정렬이 거의 정렬 된 파일에 대해서는 빠르게 수행 되기 때문이다.

실험적인 연구를 통하여 셸 정렬의 시간 복잡도는 대략 최악의 경우에는 이지만,

평균적인 경우에는 로 나타난다.

출처 : C언어로 쉽게 풀어 쓴 자료구조

이상으로 셸 정렬에 대해 알아 보았습니다.

다음 포스팅에서는 분할 정복(Divide and Conquer) 알고리즘을 바탕에 둔

합병 정렬(Merge sort)에 대해 알아 보겠습니다.