문서 편집 권한이 없습니다. 다음 이유를 확인해주세요: 요청한 명령은 다음 권한을 가진 사용자에게 제한됩니다: 사용자. 문서의 원본을 보거나 복사할 수 있습니다. [[분류:정렬]] == 개요 == 삽입 정렬은 정렬의 편차가 매우 심하다. 좋은 경우 n 만에 수행 하지만 최악의 경우 n^2 이 수행된다. 이 단점을 보완하기 위해서, 배열을 "어느정도" 정렬된 상태로 만들고 삽입 정렬을 시행하는 방식이다. [[Divide and Conquer]]의 한 방식으로 우선 배열을 정해진 개수만큼 나눈뒤, 삽입정렬을 수행하고 다시 합치면서 삽입정렬을 수행해 나간다. == 알고리즘의 개요 == # 자료리스트를 2차원배열로 나열한다. # 각 배열의 열들을 정렬한다. === 예제 === <span style="color:#0000FF;">[2 5 3 4 3 9 3 2 5 4 1 3]</span>로 리스트가 주어졌을 때 이 리스트를 셸 정렬로 정렬해 보자. <ol> <li>3행으로구성된 행렬로 나열하여 열단위로 정렬한다. {|align="center" |- | 2 5 3 4 |rowspan=3| ⇒ | 2 4 1 2 |- | 3 9 3 2 || 3 5 3 3 |- | 5 4 1 3 || 5 9 3 4 |} </li> <li>정렬된 3행 행렬을 6행렬로 나열하여 마찬가지로 열단위로 정렬한다. {|align="center" | 2 4 |rowspan=6| ⇒ | 1 2 |- | 1 2 || 2 3 |- | 3 5 || 3 4 |- | 3 3 || 3 4 |- | 5 9 || 3 5 |- | 3 4 || 5 9 |} </li> <li> 정렬된 행렬을 한 열단위로 나열해서 [[삽입 정렬]]한다. {|align="center" | 1 2 2 3 3 4 3 4 3 5 5 9 || ⇒ || 1 2 2 3 3 3 3 4 4 5 5 9 |} 이 때, 자료가 멀리 이동될 필요가 없다는 장점이 있다. </li> </ol> 여기서 마지막에는 결국에는 삽입 정렬이 사용된다. 이때 왜? 셸 소트를 사용할까 하는 의문이 발생할 수 있지만, 기본적으로 삽 입정렬은 최선의 경우 성능이 좋다는 데에서 착안하면, 그 전단계는 삽입 정렬의 최선만 사용하면서 정렬해 나가는 과정이 었다 생각하면 된다. Shell sort 문서로 돌아갑니다.