목차
- 셸 정렬이란?
- 사용 예시
- 장점과 단점
- 시간 복잡도
1. 셸 정렬이란?
가장 오래된 정렬 알고리즘의 하나입니다.
다음의 삽입 정렬에 대한 특징을 이용, 보완한 삽입 정렬의 일반화라고 생각할 수 있습니다.
• 삽입 정렬의 경우 초기에 주어진 배열이 '거의 정렬되어 있는 상태'라면 효율적이다.
• 삽입 정렬의 경우 한번에 한 원소만 정해지기 때문에 비효율적이다.
셸 정렬은 주어진 배열의 길이를 짧은 부(sub) 배열로 나누어 정렬합니다.
이 때 부 배열의 길이를 매개변수로 생각합니다.
이 과정을 매개변수가 1이 될 때 까지 반복합니다.
셸 정렬은 아래의 과정을 거칩니다.
• 데이터를 수십 개 정도로 나누어 삽입 정렬을 진행한다.
• 데이터를 다시 나누어 삽입 정렬을 진행한다.
2. 사용 예시
아래의 배열을 통해 정렬을 진행하며 설명하겠습니다.
길이가 10이기 때문에 초기 매개변수가 10인 것을 알 수 있습니다.
이 매개변수를 2로 나누어 진행하면 다음과 같은 모습으로 나타낼 수 있습니다.
매개변수가 5인 것을 확인할 수 있습니다.
이 때 매개변수를 간격으로 하는 숫자들 끼리 삽입 정렬을 진행합니다.
위 그림에서 표시된 것 처럼 한 행마다 삽입 정렬이 이루어 지는 것을 의미합니다.
매개변수가 5일때의 정렬은 끝났습니다.
이후 이 매개변수를 다시 2로 나누어 같은 과정을 반복합니다.
이후 매개변수를 다시 2로 나누어 1이 되면 간격 1의 삽입정렬을 진행합니다.
결국 평범한 삽입정렬과 다를 바가 없다고 생각할 수 있습니다.
그렇다면 위 3단계에 거쳐서 특정원소가 어떻게 이동했는지를 확인한다면 이해하기 쉽습니다.
'8'을 예시로 생각해보겠습니다.
위 그림에서 확인할 수 있듯이 한번의 과정을 거치면서 이동하는데 일반 삽입 정렬과는 다르게 한번에 이동하는 거리가 커졌습니다.
그렇기 때문에 일반적으로 삽입 정렬이 이루어지는 횟수가 줄어들게 됩니다.
3. 장점과 단점
3-1. 장점
- 위에서 설명했 듯, 자료의 교환이 이루어질 때 삽입 정렬보다 더 빠른 속도로 수행이 가능합니다.
- 통상적으로 '어느 정도 정렬이 수행된 배열'에서 사용하기 때문에 기본적인 삽입 정렬 보다 빠른 속도로 수행됩니다.
- 구현 난이도가 낮은 편입니다.
3-2. 단점
- 기존 배열에 따라 시간 복잡도가 차이가 납니다.
- 사전에 '어느 정도 정렬이 진행된 배열'인지 파악해야 할 수도 있으며 최악의 경우 삽입 정렬과 시간 복잡도가 똑같을 수 있습니다.
4. 시간 복잡도
최악의 시간 복잡도: O(N^2)
통상적 시간 복잡도: O(n long(n))
