셸 정렬(Shell Sort)

1. 셸 정렬이란?

 셸 정렬은 삽입 정렬을 개선한 방법으로, 배열의 원소들을 정렬할 때 처음부터 끝까지 순서대로 방문하면서 원소를 정렬하지 않고, Gap을 주어 부분 리스트를 만든 후 정렬하는 방식을 말한다. 이 말이 무엇인지 아래 예제를 통해 살펴보자.

 

셸 정렬 예제

 위의 예제에서 보여주는 특징은,

1) 'k'라고 하는 변수를 통해서 Gap을 조정한다.

 => 참고로 최초의 k는 보통 '배열의 길이/2'로 설정하며, 개발자가 값을 '배열의 길이/3' 또는 위와 같이 홀수로 결정하는 방법 등이 있다. 

2) 'k'만큼 떨어진 값들을 정렬한다.

3) k가 1이 될 때까지 1,2번 과정을 반복한다.

 

이렇게 3가지로 압축 할 수 있다.

 

2. 성능비교(삽입정렬 / 셸 정렬)

Name	Best	Avg	Worst	Run-time(정수 60,000개) 단위: sec
Insertion	n	n^2	n^2	7.438
Shell	n	n^1.5	n^2	0.056

 => 평균적으로 Shell Sort 방식이 기본 Insertion sort 방식보다 빠르다는걸 알 수 있다.