셸 정렬 알고리즘(Shell Sort Algorithm)

 셸 정렬 알고리즘은 삽입 정렬 알고리즘의 단점을 극복할 수 있도록 일부를 개선한 정렬 알고리즘입니다. 이 알고리즘의 성능은 삽입 정렬 알고리즘과는 비교도 되지 않을 정도로 우수합니다.

 셸 정렬은 주어진 배열을 일정 그룹으로 나눠서 1차 정렬을 하고, 1차 정렬한 배열을 다시 더 잘게 나눠서 2차 정렬을 하는 과정을 반복하는 정렬입니다. 표로 보면 이렇습니다.

	1	5	9	4	3	8	2	7	6	0
(Skip=10/3+1) 1-1	1				3				6
1-2		0				5				8
1-3			2				9
1-4				4				7
1st Result	1	0	2	4	3	5	9	7	6	8
(Skip=Skip/3+1) 2-1	1		2		3		6		9
2-2		0		4		5		7		8
2nd Result	1	0	2	4	3	5	6	7	9	8
(Skip=Skip/3+1) Final	0	1	2	3	4	5	6	7	8	9

여기서 Skip은 배열을 어느 단위로 건너뛰어서 그룹을 만들건지를 말합니다. 즉, 위에서는 1번째에서는 4씩 건너뛰고, 2번째에서는 4/3+1인 2씩 건너뛴다는 것을 말하죠. 이렇게 비교하면서 정렬하면 비교 횟수나 데이터의 이동 횟수가 훨씬 줄어듭니다.

 *셸 정렬에서 데이터를 나누는 값의 방식은 N/2와 N/3+1이 대중적인데, N/2보다 N/3+1이 더 빠르답니다.

 아래는 셸 정렬 소스코드입니다.

 소스코드를 보면 삽입 정렬 알고리즘의 소스와 대부분 흡사합니다. 셸 정렬 알고리즘은 위의 소스 코드와 같이 데이터가 많은 경우 해당 데이터를 특정한 조건으로 나누어 분할해서 정렬시키는 방식입니다. 다른 정렬 알고리즘들은 데이터 하나를 다른 데이터들과 비교한 후 필요에 따라 이동하기 때문에 O(N^2)의 성능에서 벗어나기 어렵지만, 셸 정렬 알고리즘은 O(N(logN)^2)이라는 월등한 성능을 보여줍니다. 데이터의 비교 횟수와 이동 횟수가 현저하게 줄어들기 때문입니다.