[알고리즘] 셸 정렬(shell sort)이란

growdeveloper ㅣ 2021. 10. 29. 14:30

가장 오래된 정렬 알고리즘의 하나로, 삽입정렬을 보완한 알고리즘

Goal

▶ 셀 정렬(shell sort) 알고리즘의 개념 요약

Donald L.Shell 이라는 사람이 제안한 방법으로, 삽입정렬을 보안한 알고리즘이다.
삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안
- 삽입 정렬의 최대 문제점: 요소 들이 삽입될때, 이웃한 위치로만 이동
- 즉, 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있다.
- 삽입 정렬과 다르게 셀 정렬은 전체의 리스트를 한 번에 정렬하지 않는다.
과정 설명
1. 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류
2. 연속적이지 않은 여러 개의 부분 리스트를 생성
3. 각 부분 리스트를 삽입 정렬을 이용하여 정렬
4. 모든 부분 리스트가 정렬되면 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만들 후에 알고리즘을 반복
5. 위의 과정을 부분 리스트의 개수가 1이 될 때까지 반복

▶ 셀 정렬(shell sort) 알고리즘의 구체적인 개념

정렬해야 할 리스트의 각 k번재 요소를 추출해서 부분 리스트를 만든다. 이떄, k를 '간격(gap)' 이라고 한다
- 간격의 초깃값: (정렬할 값의 수)/2
- 생성된 부분 리스트의 개수는 gap과 같다.
각 회전마다 간격 k를 절반으로 줄인다, 즉, 각 회전이 반볼될 대마다 하나의 부분 리스트에 속한 값들의 개수는 증가한다.
- 간격은 홀수로 하는 것이 좋다.
- 간격을 절반으로 줄일 때 짝수가 나오면 +1을 해서 홀수로 만든다.
간격 k가 1이 될떄까지 반복한다.

▶셸 정렬(shell sort) 알고리즘의 예제

배열에 10, 8, 6, 20, 4, 3, 22, 1, 0, 15, 16이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.
1회전
- 처음 간격을(정렬할 값의 수:10)/2 = 5로 하고, 다섯 번째 요소를 추출해서 부분 리스트를 만든다. 만들어진 5개의 부분리스트를 삽입 정렬로 정렬한다.
2회전
- 다음 간격은 = (5/2: 작수) + 1 = 3으로 하고, 1 회전 정렬한 리스트에서 세 번재 요소를 추출해서 부분 리스트를 만든다. 만들어진 3개의 부분 리스트를 삽입 정렬로 정렬한다.
3회전
- 다음 간격은 = (3/2) = 1 으로 하고, 간격 k 가 1 이므로 마지막으로 정렬을 수행한다. 만들어진 1개의 부분 리스트를 삽입 정렬로 정렬한다.

▶셸 정렬(shell sort) 코드

▶셸 정렬(shell sort) 알고리즘의 특징

장점
1. 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동한다. 따라서 교환되는 요소들이 삽입 정렬보다는 최종 위치에 있을 가능성이 높아진다.
2. 부분 리스트는 어느 정도 정렬이 된 상태이기 때문에 부분 리스트의 개수가 1이 되게 되면 셀정렬은 기본적으로 삽입 정렬을 수행하는 것이지만 삽입 정렬보다 더욱 빠르게 수행된다.
3. 알고리즘이 간단하여 프로그램으로 쉽게 구현할 수 있다

▶셸 정렬(shell sort)의 시간 복잡도

시간복잡도를 계산한다면

평균: T(n) = O(n^1.5)
최악의 경우: T(n) = O(n^2)