[5.23] 06-5 셸 정렬

06-5 셸 정렬

셸 정렬 shell sort

 

단순 삽입 정렬의 문제

삽입 위치가 멀리 떨어져 있으면 이동 횟수가 많아짐

 

셸 정렬 알아보기

shell sort 알고리즘 - 정렬할 배열의 우너소를 그룹으로 나눔. 그룹별로 정렬 수행. 정렬된 그룹을 합치는 작업을 반복함. 

4정렬 -> 2정렬 -> 1정렬을 적용하면 정렬이 완료된다. 'h-정렬'

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
  return a


print(shell_sort([2, 4, 5, 1, 3, 6]))

셸 정렬 알고리즘 구현하기 - h * 3 + 1 수열로 h값 선택함

from typing import MutableSequence

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

  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 //= 2
  return a


print(shell_sort([2, 4, 5, 1, 3, 6]))