Shell Sort: 쉘 정렬

* Shell Sort?

이미치 출처  https://gfycat.com/ko/dishonesthighlevelfruitbat

쉘 정렬은 전체의 리스트를 한 번에 정렬하지 않는다. 

1. 정렬해야할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다. 

2. 모든 부분 리스트가 정렬되면 쉘 정렬은 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 되풀이한다. 

3. 부분 리스트의 개수가 1이 될 때까지 이 과정을 반복한다. 

 

 

부분 리스트를 만들 때에는 주어진 리스트의 k번째 요소를 추출하여 만든다. 이 k번째 요소를 간격(gap)이라고 한다. 이 간격은 처음에는 자료의 개수가 n개 있다면 n / 2 정도로 정하고 각 패스마다 간격을 절반으로 줄이는 방식을 많이 사용한다. 

 

* Pseudocode

 

 

* 분석

삽입 정렬에 비하여 쉘 정렬은 2가지의 장점이 있다. 

• 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동한다. 반면 삽입 정렬에서는 한번에 한 칸씩만 이동된다 따라서 교환되는 아이템들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 높아진다.
• 부분 리스트는 어느 정도 정렬이 된 상태이기 때문에 부분 리스트의 개수가 1이 되게 되면(gap이 1이 되게 되면) 쉘 정렬은 기본적으로 삽입 정렬을 수행하는 것이지만 빠르게 수행된다. 이것은 삽입 정렬이 거의 정렬된 리스트에 대해서는 빠르게 수행되기 때문이다. 

평균적인 경우에는 O(n ^ 1.5) 정도의 시간 복잡도를 가지지만 최악의 경우에는 O(n^2)의 시간 복잡도를 가질 수 있다.