Ahn9807: 새 문서: 분류:정렬 == 개요 == 삽입 정렬은 정렬의 편차가 매우 심하다. 좋은 경우 n 만에 수행 하지만 최악의 경우 n^2 이 수행된다. 이 단점을 보완하기 위해서, 배열을 "어느정도" 정렬된 상태로 만들고 삽입 정렬을 시행하는 방식이다. Divide and Conquer의 한 방식으로 우선 배열을 정해진 개수만큼 나눈뒤, 삽입정렬을 수행하고 다시 합치면서 삽입정렬을 수행해 나간다....

2023-03-24T11:49:36Z

새 문서: 분류:정렬 == 개요 == 삽입 정렬은 정렬의 편차가 매우 심하다. 좋은 경우 n 만에 수행 하지만 최악의 경우 n^2 이 수행된다. 이 단점을 보완하기 위해서, 배열을 "어느정도" 정렬된 상태로 만들고 삽입 정렬을 시행하는 방식이다. Divide and Conquer의 한 방식으로 우선 배열을 정해진 개수만큼 나눈뒤, 삽입정렬을 수행하고 다시 합치면서 삽입정렬을 수행해 나간다....

새 문서

[[분류:정렬]]

== 개요 ==
삽입 정렬은 정렬의 편차가 매우 심하다. 좋은 경우 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 - 편집 역사