정렬 - 4 [ 셸 정렬 ]

셸 정렬(Shell Sort)이란?

단순 삽입 정렬의 장점은 살리고 단점은 보완하여 좀 더 빠르게 정렬하는 알고리즘입니다.

 

삽입 정렬에 장단점으로  초기에 시간이 오래 걸리지만 정렬이 마칠 때 쯤이면 속도가 빨리집니다.

그러나 삽입할 위치가 멀리 떨어져 있다면 이동해야 되는 횟수가 많아집니다. (전체적으로 이동시켜야 되기 때문에)

 

셸 정렬은 삽입 정렬의 장점을 살리고 단점을 보완한 알고리즘이라고 생각하시면 됩니다.

 

먼저 정렬할 배열의 요소를 그룹으로 나눠 각 그룹 별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법입니다.

 

아래 그림을 통해서 셸 정렬이 어떤식으로 동작하는 확인해보겠습니다.

 

 

 

그림을 통해서 확인했듯이 전체적으로 움직이는 횟수가 많이 줄어든 것을 확인 할 수 있습니다.

 

증분값이라고 위에 그림에서는 4 , 2  ,1칸만큼 나눈 값을 증분값이라고 합니다.

증분값은 마지막에는 항상 1이 되야되며 효율적으로 동작하기 위해서는 서로 배수가 아니여야 됩니다.

또한 증분값 초기값이 너무 크면 효과가 없기 때문에 배열의 요소수를 9로 나눈 값을 넘지 않도록 설정하였습니다.

 

 

셸 정렬 소스 코드

https://github.com/jokerKwu/java/blob/master/JavaStructure/src/ShellSort.java