8-3) 정렬 - 셸 정렬

 

아래 내용은 부스트코스 <자바로 구현하고 배우는 자료구조> 강의를 들으며 정리한 것입니다.

 

셸 정렬 (Shell sort)

삽입 정렬을 약간 변형한 정렬. 일정한 너비만큼 떨어진 요소를 가져와서 그 둘을 대소비교한 후 바꾸는 방법이다. (일정 너비만큼 모두 바꾸면 1round) 간격의 크기를 점점 줄이며 정렬하다 간격 크기가 1이 되면 삽입 정렬을 한다. 요소의 이동 횟수를 줄이는 데 의의가 있다. 즉, 거의 정렬된 상태로 만들어 삽입 정렬을 하는 경우 시간 복잡도가 크게 줄어드는 것을 활용하는 방식이다. 

 

1round 정렬 후 - 3 2 8 5 7 6 10 9 1&nbsp; (1은 혼자 남음)

 

셸 정렬은 리스트 안에서 순서만 바꾸기 때문에 in-place 정렬이며, 중복된 숫자의 순서가 보장되지 않는 불안정 정렬이다.

 

셸 정렬의 평균적인 시간 복잡도는 사용하는 간격의 크기에 따라 바뀌는데, O(n^5/4) 혹은 O(n^3/2)가 된다. Worst case에서 셸 정렬은 기본적으로 삽입 정렬과 같으므로 O(n^2)에 가까워진다. 

 

셸 정렬은 구현이 까다롭고 갭 시퀀스에 영향을 많이 받는다는 점이 단점이다.  효율적인 셸 정렬의 Best gap sequence에 대해 연구한 결과들을 많이 살펴볼 수 있다.

Shellsort - Wikipedia