셸 정렬

셸 정렬

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

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

1. 셸 정렬은 먼저 정렬할 배열의 원소를 그룹으로 나눠 각 그룹별 정렬을 수행한다.

2. 그 후 정렬 된 그룹을 합치는 작업을 반복하여 원소의 이동 횟수를 줄인다.

   1.시간 복잡도는 O(n^1.25)이지만 떨어져 있는 원소를 서로 교환하므로 안정적이지 않다.

   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