개요
삽입 정렬은 정렬의 편차가 매우 심하다. 좋은 경우 n 만에 수행 하지만 최악의 경우 n^2 이 수행된다. 이 단점을 보완하기 위해서, 배열을 "어느정도" 정렬된 상태로 만들고 삽입 정렬을 시행하는 방식이다. Divide and Conquer의 한 방식으로 우선 배열을 정해진 개수만큼 나눈뒤, 삽입정렬을 수행하고 다시 합치면서 삽입정렬을 수행해 나간다.
알고리즘의 개요
- 자료리스트를 2차원배열로 나열한다.
- 각 배열의 열들을 정렬한다.
예제
[2 5 3 4 3 9 3 2 5 4 1 3]로 리스트가 주어졌을 때 이 리스트를 셸 정렬로 정렬해 보자.
- 3행으로구성된 행렬로 나열하여 열단위로 정렬한다.
2 5 3 4 ⇒ 2 4 1 2 3 9 3 2 3 5 3 3 5 4 1 3 5 9 3 4 - 정렬된 3행 행렬을 6행렬로 나열하여 마찬가지로 열단위로 정렬한다.
2 4 ⇒ 1 2 1 2 2 3 3 5 3 4 3 3 3 4 5 9 3 5 3 4 5 9 -
정렬된 행렬을 한 열단위로 나열해서 삽입 정렬한다.
1 2 2 3 3 4 3 4 3 5 5 9 ⇒ 1 2 2 3 3 3 3 4 4 5 5 9 이 때, 자료가 멀리 이동될 필요가 없다는 장점이 있다.
여기서 마지막에는 결국에는 삽입 정렬이 사용된다. 이때 왜? 셸 소트를 사용할까 하는 의문이 발생할 수 있지만, 기본적으로 삽 입정렬은 최선의 경우 성능이 좋다는 데에서 착안하면, 그 전단계는 삽입 정렬의 최선만 사용하면서 정렬해 나가는 과정이 었다 생각하면 된다.