셸 정렬

삽입 정렬의 장단점을 보면,

장점 : 거의 정렬은 마친 상태에서는 속도가 굉장히 빠르다.

단점 : 타겟 요소가 이전 요소들(정렬된)보다 작으면 이동하는 횟수가 많아진다.

 

셸 정렬은 단점을 보완하고 장점을 살리기 위해 고안된 정렬 알고리즘이다.

 

삽입 위치가 멀 경우, 한 칸씩 비교하면서 교환하는 것이 오래 걸리기 때문에,

일정 간격으로 띄엄띄엄 비교/교환을 한다는 아이디어다. 그리고 이 간격을 줄여가다보면 정렬이 완료될 것이다.

 

1. 얼만큼 띄어가면서 검사할 지 간격을 정한다.

2. 해당 간격만큼 요소들을 띄워 묶어서 그룹 별로 나눈다.

3. 나눈 그룹 별로 각자 삽입 정렬을 한다.

4. 적당한 간격으로, 적당한 횟수만큼 진행하여 거의 정렬된 배열을 만든다.

5. 최종적으로 1을 간격으로 하여 삽입 정렬을 한다. 

 

거의 정렬된 배열에서는 속도가 빠른 삽입정렬의 장점을 활용한다.

 

일정 간격을 두고 비교/교환이 일어나므로 불안정하다.

 

시간 복잡도는 간격, 진행 횟수에 따라 다르므로 구하는 것이 복잡하다.

최악의 경우는 일반 삽입 정렬과 같은 경우로 O(N^2)일 것이다.