셸 정렬 (Shell Sort)

셸 정렬 (Shell Sort)

 

 

셸 정렬 (Shell Sort)에 대해서는 학교 수업시간에 학습한 개념이지만, 겉핥기 식으로만 학습하였고,

또 백준 알고리즘 문제를 해결하다보니 기존에 학습한 기본적인 정렬 (삽입, 선택, 버블)로는

대부분 시간초과로 통과하지 못하였기에 더 빠른 정렬을 이용하고자 다시 제대로 학습하게 되었다.

 

우선 셸 정렬 (Shell Sort)는 1959년, 이 방법을 고안한 "도널드 셸"의 이름을 따서 붙여졌고,

기존의 삽입 정렬(Insertion Sort)의 단점을 보완하고자 개발되었다.

 

 

<기존의 삽입 정렬의 문제점>

1. 정렬이 하나도 되어 있지 않은 경우 매우 비효율적

2. 삽입되어야 할 위치가 멀리 있다면 원소들의 많은 이동을 해야만 삽입 가능

 

(삽입 정렬 Review)

 

 주어진 배열에서 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열부분과 비교하여

자신의 위치를 찾아 삽입함으로써 정렬하는 알고리즘

 

위의 그림에서 4번과 같은 경우에 1이 자신의 자리로 찾아가기 위해서는

2,3,5,7이 모두 이동해야 하기 때문에 효율적이지 못하다.

 

 

 

셸 정렬 (Shell Sort) 알고리즘의 동작 원리

 

<Main> 배열을 그룹을 지어서 각각의 그룹별로 '삽입 정렬'을 수행

 

i. 데이터를 특정한 간격에 있는 원소들끼리 묶어 그룹화를 하여 부분 리스트를 만든다. 

(이 때, 이 간격을 'gap' 이라고 한다.)

ii. 각 부분 리스트별로 삽입 정렬을 수행한다. 

iii. 그 후 데이터를 다시 gap = gap/2, 즉 이전의 gap의 절반으로 원소들끼리 묶는다.

(이 때, gap은 가능한 홀수로 만들어 주는 것이 효율적이다.

ex) 5/2 = 2 이므로 정렬이 덜 된 경우에, gap이 작을 수록 더 수행시간이 오래 걸리므로 gap에 1을 더해 3으로 만든다.)

iv. 모든 부분 리스트의 원소가 1개가 될 때까지 ii~iii을 반복한다.

 

(위의 예시에서는 gap을 1씩 줄여가면서 부분 리스트를 만들었고,

같은 부분 리스트의 원소는 동일한 색으로 나타내었다.)

 

 

셸 정렬 (Shell Sort) 알고리즘의 장점

 

1) gap이 1이 아닌 그룹의 경우, 원소의 교환이 발생할 때 더 큰 거리를 이동하게 된다. (gap에 의해)

-> 기존의 삽입 정렬보다는 해당 원소가 최종적인 위치에 있을 가능성이 높아진다.

2) gap = 1인 경우 삽입 정렬과 동일하지만, 어느 정도 정렬이 된 상태이기 때문에 삽입 정렬보다

   더 빠르게 수행된다. (n이 클 수록 더욱 효율적)

3) 알고리즘이 크게 어렵지 않고 간단하다.

Tip) gap = gap/2를 가장 흔히 사용하지만, gap = gap/3 + 1이 더 빠르다고 알려져 있다고 한다.

 

 

※ 시간 복잡도 : 최선의 경우 O(nlogn)  / 평균 O(n^1.5)  / 최악의 경우 O(n^2)

 - 평균이 O(n^1.5)이므로 삽입, 선택, 버블 정렬보다 빠르게 수행이 된다. 최악의 경우 O(n^2)이지만,

   백준 문제를 여러 개 풀어 본 결과 많은 경우 시간 내에 통과가 되었다.

 

 

셸 정렬 (Shell Sort) 알고리즘 코드 (C 언어)