쉘 정렬

쉘정렬(Shell Sort)

쉘 정렬은 삽입정렬의 단점을 보완하기 위해 만든 정렬 방법이다.

 

“삽입 정렬을 하기 전에 미리 정리를 해놓자!”

 

어떻게 정리를 한단 말인가?

삽입 정렬은 모든 원소에 대해서 검사를 하지만, 쉘 정렬의 경우, 앞에서 구한 어떠한 간격만큼 떨어진 원소에 대해서 삽입정렬을 먼저 수행하고, 그 간격을 점점 줄여 계속 삽입정렬을 하는 방법을 취한다.

간격은 결국 1이 될 것이며, 1이 되는 때는 곧, 삽입 정렬을 수행하는 것과 동일하다.

 

45, 39, 98, 15, 52, 44, 33, 28, 40, 38, 77, 68, 11, 43

위와 같은 수들이 있다. 간격을 5, 3, 1로 놓고 삽입 정렬을 시작할 것이다.

 

1) 간격이 5일 경우, 같은 묶음 끼리 같은 색으로 표시해보면

45, 39, 98, 15, 52, 44, 33, 28, 40, 38, 77, 68, 11, 43

위와 같다.

묶음 1 : 45, 44, 77 => 44, 45, 77

묶음 2 : 39, 33, 68 => 33, 39, 68

묶음 3 : 98, 28, 11 => 11, 28, 98

묶음 4 : 15, 40, 43 => 15, 40, 43

묶음 5 : 52, 38 => 38, 52

각 묶음으로 정렬을 수행 한다.

44, 33, 11, 15, 38, 45, 39, 28, 40, 52, 77, 68, 98, 43

 

2) 간격이 3일 경우, 같은 묶음 끼리 같은 색으로 표시해보면

44, 33, 11, 15, 38, 45, 39, 28, 40, 52, 77, 68, 98, 43

 

묶음1 : 44, 15, 39, 52, 98 => 15, 39, 44, 52, 98

묶음2 : 33, 38, 28, 77, 43 => 28, 33, 38, 43, 77

묶음3 : 11, 45, 40, 68 => 11, 40, 45, 68

 

각 묶음으로 정렬을 수행한다.

15, 28, 11, 39, 33, 40, 44, 38, 45, 52, 43, 68, 98, 77

 

3) 간격이 1일 경우

보통의 삽입 정렬을 수행한다.

 

그렇다면 간격은 어떻게 설정하나?

간격을 어떻게 설정하는지에 따라서 성능에 중요한 영향을 끼친다. 배열의 길이를 토대로 잡는다면

첫 번째 간격을 N/2, 두 번째 간격을 N/4 ... 등으로 잡는 방법이 있다.

 

시간 복잡도?

삽입정렬의 O(n^2)보다는 우수하지만 가장 효율적인 정렬 알고리즘의 O(nlogn)에는 미치지 못한다.

O(n^(4/3)) 정도이다. 또한 increments sequence를 어떻게 하느냐에 따라 성능이 좌우되는데 sequence가 좋지 않는 최악의 경우 복잡도는 O(n^2)가 되어 버린다.