개발바닥

셸 정렬(Shell Sort)이란? 단순 삽입 정렬의 장점은 살리고 단점은 보완하여 좀 더 빠르게 정렬하는 알고리즘입니다. 삽입 정렬에 장단점으로 초기에 시간이 오래 걸리지만 정렬이 마칠 때 쯤이면 속도가 빨리집니다. 그러나 삽입할 위치가 멀리 떨어져 있다면 이동해야 되는 횟수가 많아집니다. (전체적으로 이동시켜야 되기 때문에) 셸 정렬은 삽입 정렬의 장점을 살리고 단점을 보완한 알고리즘이라고 생각하시면 됩니다. 먼저 정렬할 배열의 요소를 그룹으로 나눠 각 그룹 별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법입니다. 아래 그림을 통해서 셸 정렬이 어떤식으로 동작하는 확인해보겠습니다. 그림을 통해서 확인했듯이 전체적으로 움직이는 횟수가 많이 줄어든 것을..