쉘 정렬(Shell Sort)

삽입 정렬의 단점을 보완한 정렬 방식.

삽입 정렬의 단점???

삽입 정렬은 한칸씩 이동하면서 비교하기 때문에 만일 가장 멀리 떨어진 곳에서 비교가 이루어진다면 이동 시 많은 오버헤드가 발생할 수 있다. 

그 단점을 보완하기 위해 만들어진 방식!!

그림과 함께 살펴보도록 하자

1. 주어진 배열에 대해 반으로 쪼갠 후, 쪼갠 블록을 각 쌍으로 삽입 정렬을 시행한다.

예를 들면 {3,2}, {8,1}, {0,4} 가 쌍으로 삽입 정렬이 실행되고 결과는 {2,3}, {1,8}, {0,4} 로 나타날 것이다.

2. 삽입 정렬이 완료된 블록에 대해 다시 반으로 쪼갠 후, 쪼갠 블록의 각 index를 다시 삽입 정렬로 정렬한다.

{2,1,3,8}, {0,4} => {1,2,3,8}, {0,4}

3. 결과에 대해 다시 반으로 쪼갠 후, 삽입 정렬을 한다.

{1,2,0,3,8,4} => {0,1,2,3,4,8}

상당히 간단한 알고리즘으며, '저게 기존 삽입 정렬보다 어떻게 성능이 좋다는 거지??' 라는 의문이 들 수도 있을 것이다.

지금은 간단한 길이의 배열이며, 만약에 저 수가 크다면 성능 차이가 제대로 나타난다....라고들 한다. 

(나도 아직 안해본거라서..)

일단 삽입 정렬 같은 경우에는 많아야 한 칸씩 움직이는게 전부인데 반해, 쉘 정렬은 범위를 어떻게 정하느냐에 따라 한번에 많은 이동이 가능하다. 그렇기 때문에 삽입 정렬보다 더 효율적이라고 할 수 있다.