쉘 정렬(Shell Sort)

쉘 정렬(Shell Sort)

쉘 정렬은 Donald L. Shell 이라는 사람이 제안한 방법으로 삽입 정렬이 어느정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안한 방법입니다.

쉘 정렬의 속도는 삽입정렬의 O(n^2)보다 빠릅니다. 

쉘 정렬의 속도는 약 O(n^1.5) : 몇개로 그룹들을 나누느냐에 따라 실행속도가 달라집니다.

삽입정렬의 최대 문제점은 요소들이 삽입될 때 이웃한 위치로만 이동한다는 것입니다.

만약, 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 이미 정렬된 요소들이 많은 이동을 해야만이 제자리로 삽입될 수 있습니다.

- 정렬 위치 이후의 모든 요소들이 한 칸씩 옆으로 이동해야 정렬이 됨

쉘 정렬은 요소들이 멀리 떨어진 위치로 이동할 수 있습니다.

1. 정렬해야 할 리스트들을 일정한 기준에 따라 여러개의 부분 리스트로 구성

2. 각 부분 리스트를 삽입정렬을 이용해 정렬

3. 부분 리스트가 정렬되면 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만듬

4. 부분 리스트의 개수가 1이 될 때까지 2를 반복

부분리스트로 나누고 -> 삽입정렬하고 -> 다시 더 작은 부분리스트로 나누고 -> 삽입정렬하고를 반복하는 형태로 이루어집니다.

쉘 정렬의 특징

삽입정렬에 비해 쉘 정렬은 2가지의 장점이 있습니다.

1. 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동하지만, 삽입정렬에서는 한번에 한칸씩만 이동됩니다.

- 교환되는 아이템들이 삽입정렬보다는 최종위치에 더 가까이 있을 가능성이 높아집니다.

2. 부분 리스트는 어느정도 정렬이 된 상태이기 때문에 부분 리스트의 개수가 1이 되게 되면 쉘 정렬은 기본적으로 삽입정렬을 수행하는 것이지만 빠르게 수행 됩니다.

- 삽입정렬이 거의 정렬된 리스트에 대해서는 빠르게 수행되기 때문

앞서 말씀드린대로 삽입 정렬에 비해 빠르지만 O(n^1.5), 최악의 경우에는 삽입정렬과 똑같은 O(n^2)의 속도가 나오기도 합니다.

쉘 정렬 구현

출처 : http://wonjayk.tistory.com/220