[Algorithm] 정렬 알고리즘_5(셸 정렬)

06-5 셸 정렬

단순 삽입 정렬의 특징

• 장점: 이미 정렬을 마쳤거나 정렬이 거의 끝나가는 상태에서는 속도가 아주 빠릅니다.
• 단점: 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아집니다.

셸 정렬 알아보기

셸 정렬(shell sort): 단순 삽입 정렬의 장점은 살리고 단점은 보완하여 더 빠르게 정렬하는 알고리즘

셸 정렬은 단순 삽입 정렬의 장점을 살리고 단점을 보완하기 위해 사용합니다. 정렬 횟수는 늘어나지만 전체적으로 원소의 이동 횟수가 줄어들어 효율적입니다. 

실습 6-8 셸 정렬 알고리즘 구현하기

# 셸 정렬 알고리즘 구현하기


from typing import MutableSequence

def shell_sort(a: MutableSequence) -> None:
  """셸 정렬"""
  n = len(a)
  h = n // 2
  while h > 0:
    for i in range(h, n):
      j = i - h
      tmp = a[i]
      while j >= 0 and a[j] > tmp:
        a[j + h] = a[j]
        j -= h
      a[j + h] = tmp
    h //= 2

if __name__ == '__main__':
  print('셸 정렬을 수행합니다.')
  num = int(input('원소 수를 입력하세요.: '))
  x = [None] * num                # 원소 수가 num인 배열을 생성

  for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

  shell_sort(x)        # 배열 x를 이진 삽입 정렬

  print('오름 차순으로 정렬헀습니다.')
  for i in range(num):
    print(f'x[{i}] = {x[i]}')

셸 정렬을 수행합니다.
원소 수를 입력하세요.: 8
x[0]: 8
x[1]: 1
x[2]: 4
x[3]: 2
x[4]: 7
x[5]: 6
x[6]: 3
x[7]: 5
오름 차순으로 정렬헀습니다.
x[0] = 1
x[1] = 2
x[2] = 3
x[3] = 4
x[4] = 5
x[5] = 6
x[6] = 7
x[7] = 8

10 ~ 17행 (for i in range(h, n) ~ h // = 2)은 단순 삽입 정렬을 수행하는 과정으로 실습 6-7의 08 ~ 14행과 거의 같습니다. 다른 점이 있다면 주목하는 원소와 비교하는 원소가 서로 이웃하지 않고 h개만큼 떨어져 있다는 것입니다.

08행에서 h의 초깃값은 n // 2로 구합니다(전체 배열의 절반값입니다). 그리고 while 문을 반복할 때마다 다시 2로 나눈 값으로 업데이트합니다. 즉. h는 다음과 같이 변화합니다.

• 원소 수가 8이면 4 → 2 → 1
• 원소 수가 7이면 3 → 1

---

h값의 선택

h값은 n부터 감소하다가 마지막에는 1이 됩니다. 그렇다면 h값을 어떤 수열로 감소시키면 효율적인 정렬을 할 수 있을지 알아봅시다.

셸 정렬에서 그룹 나누기(h = 4, 2, 1)

위 그림 a를 학생 8명의 점수라고 가정합시다. 먼저 그림 b처럼 학생 2명씩 4개 그룹으로 나누어 정렬합니다. 그런 다음 그림 c처럼 학생 4명씩 2개 그룹으로 나누어 다시 정렬합니다.

그림에서 파란색 그룹((8, 7), (4, 3))과 검은색 그룹((1, 6), (2, 5))은 섞이지 않습니다. 그런데 이렇게 두 그룹이 섞이지 않은 상태에서 c로 합치면 다시 처음 단계인 a와 같아집니다. 이는 애써 그룹으로 나누어서 정렬했지만 충분히 그 기능을 하지 못한다는 것을 보여 줍니다.

이 문제를 해결하려면 h값이 서로 배수가 되지 않도록 해야 합니다. 그러면 원소가 충분히 뒤섞이므로 효율 좋은 정렬을 기대할 수 있습니다. 

실습 6-9 셸 정렬 알고리즘 수현하기(h * 3 + 1의 수열 사용)

# 셸 정렬 알고리즘 구현하기(h * 3 + 1의 수열 사용)

from typing import MutableSequence

def shell_sort(a: MutableSequence) -> None:
  n = len(a)
  h = 1

  while h < n // 9:
    h = h * 3 + 1

  while h > 0:
    for i in range(h, n):
      j = i - h
      tmp = a[i]
      while j >= 0 and a[j] > tmp:
        a[j + h] = a[j]
        j -= h
      a[j + h] = tmp
    h //= 3

if __name__ == '__main__':
  print('셸 정렬을 수행합니다.(h * 3 + 1의 수열 사용')
  num = int(input('원소 수를 입력하세요.: '))
  x = [None] * num                # 원소 수가 num인 배열을 생성

  for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

  shell_sort(x)        # 배열 x를 이진 삽입 정렬

  print('오름 차순으로 정렬헀습니다.')
  for i in range(num):
    print(f'x[{i}] = {x[i]}')

셸 정렬을 수행합니다.(h * 3 + 1의 수열 사용
원소 수를 입력하세요.: 8
x[0]: 8
x[1]: 1
x[2]: 4
x[3]: 2
x[4]: 7
x[5]: 6
x[6]: 3
x[7]: 5
오름 차순으로 정렬헀습니다.
x[0] = 1
x[1] = 2
x[2] = 3
x[3] = 4
x[4] = 5
x[5] = 6
x[6] = 7
x[7] = 8

• 10 ~11행: 이 while 문에서는 h의 초깃값을 구합니다. 1부터 시작해서 h * 3 + 1의 수열을 사용하는 작업을 반복하지만 n // 9를 넘지 않는 최댓값을 h에 대입합니다.
• 13 ~ 21행: 실습 6-8에서 작성한 while 문과 거의 같습니다. 다른 점은 h값이 변하는 방법입니다. 21행에서 h값을 3으로 나누는 작업을 반복해서 결국에 h값은 1이 됩니다.

셸 정렬의 시간 복잡도는 O(n의 1.25승)이고 다순 정렬의 시간 복잡도인 O(n²)보다 매우 빠릅니다. 그러나 셸 정렬 알고리즘은 이웃하지 않고 떨어져 있는 원소를 서로 교환하므로 안정적이지 않습니다.

- 출처: Do it! 자료구조와 함께 배우는 알고리즘 입문 - 파이썬 편
- notebook ipynb file:
https://github.com/heejvely/Algorithm/blob/main/Do_it_algorithm/Do_it_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.ipynb

GitHub - heejvely/Algorithm: 파이썬 알고리즘 인터뷰 책을 참고한 파이썬 알고리즘 연습