감자튀김 공장🍟

내용 정리 ➡ 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

쉘 정렬 쉘 정렬은 삽입 정렬의 O(n^2)보다 빠르다. 셀 정렬은 정렬해야할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다. 모든 부분 리스트가 정렬되면 쉘 정렬은 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 되풀이 한다. 위 과정을 부분 리스트의 개수가 1일 때까지 반복한다. 부분 리스트 구성 방법 주어진 리스트의 각 k번째 요소를 추출하여 만든다. 이 k를 간격(gap)이라고 한다. 각 스텝마다 간격 k를 줄여가므로 수행과정이 반복될 때마다 하나의 부분 리스트에 속하는 레코드들의 개수는 증가된다. 쉘 정렬의 과정 1단계 간격(gap)을 5로 잡고 {10, 3, 16}, {8, 22},..