[python] 셸 정렬(Shell sort)

Algorithm/정렬

[python] 셸 정렬(Shell sort)

Potato potage 2022. 3. 22. 22:21

내용 정리 ➡ https://good-potato.tistory.com/40

[C++] 쉘 정렬 (Shell Sort)

쉘 정렬 쉘 정렬은 삽입 정렬의 O(n^2)보다 빠르다. 셀 정렬은 정렬해야할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬

good-potato.tistory.com

코드 정리

# 쉘 정렬
def shell(arr):
  n = len(arr)
  h = n // 2
  
  while h > 0:
    for i in range(h, n):
      j = i - h
      tmp = arr[i]
      while j >= 0 and arr[j] > tmp:
        arr[j + h] = arr[j]
        j -= h
      arr[j + h] = tmp
    h //= 2

저작자표시