Python에서 Hill 정렬 알고리즘을 구현하는 방법

알고리즘 설명

"증분 정렬 감소"라고도 불리는 힐 정렬은 삽입 정렬을 최적화하여 생성된 정렬 알고리즘입니다. 실행 아이디어는 배열의 요소를 아래 첨자 증분으로 그룹화하고, 각 요소 그룹을 삽입 및 정렬하고, 증분을 줄이고, 증분이 1에 도달할 때까지 이전 단계를 반복하는 것입니다.

일반적으로 Hill 정렬의 시간 복잡도는 증분 크기에 따라 O(n1.3)~O(n2)입니다. Hill 정렬의 공간 복잡도는 O(1)로 불안정한 정렬 알고리즘입니다. Hill 정렬을 수행할 때 요소의 한 번의 이동은 여러 요소에 걸쳐 있을 수 있으며, 이는 여러 이동을 상쇄하고 효율성을 향상시킬 수 있습니다.

다음은 (배열 길이/2)를 초기 증분으로 사용하는 오름차순 Hill 정렬입니다. 각 정렬 후에 증분은 절반으로 줄어듭니다.

1단계:

그림 2-28에 표시된 대로 첫 번째 요소부터 시작하여 4씩 증가하여 그룹화합니다. 증분이 4인 경우 그룹에 요소가 두 개만 있고 그렇지 않으면 요소의 첨자가 배열 범위를 초과한다는 것을 알 수 있습니다.

2단계:

그림 2-29와 같이 그룹의 요소에 대해 삽입 정렬을 수행합니다.

3단계:

그림 2-30과 같이 계속해서 동일한 방법으로 그룹화하고, 그룹에 요소를 삽입하고 정렬하여 순서대로 만듭니다.

전체 배열의 모든 숫자를 순회한 후 이 정렬 라운드가 종료됩니다. 증분을 절반으로 줄이고 다음 정렬 라운드를 계속합니다.

4단계:

그림 2-31과 같이 증분량이 2가 되면 각 그룹의 요소가 증가하고 전체 그룹 수가 감소하는 것을 알 수 있습니다. 각 그룹을 탐색할 때까지 각 그룹의 요소를 계속해서 삽입 정렬합니다.

5단계:

그림 2-32에 최종 정렬 단계가 표시됩니다. 이때 증분은 1이 됩니다. 이는 전체 배열의 삽입 정렬과 같습니다. 즉, 마지막 라운드 정렬입니다.

마지막 정렬을 마치고 전체 힐 정렬이 끝났습니다.

코드 구현

for 루프에서는 각 그룹의 첫 번째 요소를 삽입하고 정렬할 필요가 없고 해당 첨자가 0에서 step-1 사이이므로 순회는 첨자 단계부터 시작됩니다.

순서도에서 접근 방식을 시뮬레이션하려면 두 개의 루프를 사용해야 한다는 점에 유의해야 합니다. 첫 번째 그룹을 사용한 다음 동일한 그룹의 요소를 한 번에 주문합니다. 효율성을 높이기 위해 숫자를 탐색할 때마다 해당 숫자가 위치한 그룹을 삽입하고 정렬하는 for 루프를 직접 사용합니다. 이 순회는 삽입 정렬의 순서 요구 사항도 충족합니다. 삽입 정렬에서는 현재 첨자의 값을 변경해야 하므로 for 루프에 영향을 미치지 않도록 현재 첨자를 저장하는 데 변수 ind가 사용됩니다.

일반 삽입 정렬은 1 증분의 Hill 정렬과 동일합니다. 요소 전체의 Hill 정렬은 실제로 증분만 변경하며 논리적으로 일반 삽입 정렬과 다르지 않습니다.

Hill 정렬 코드:

nums = [5,3,6,4,1,2,8,7]
def ShellSort(nums):
  step = len(nums)//2　　　　　　　　 #初始化增量为数组长度的一半
  while step > 0:　　　　　　　　　　 #增量必须是大于0的整数
   for i in range(step,len(nums)):　#遍历需要进行插入排序的数
     ind = i
     while ind >= step and nums[ind] < nums[ind-step]: #对每组进行插入排序
      nums[ind],nums[ind-step] = nums[ind-step],nums[ind]
      ind -= step
   step //= 2　　　　　　　　　　　#增量缩小一半
  print(nums)
ShellSort(nums)

프로그램을 실행하면 출력 결과는 다음과 같습니다.

[1,2,3,4,5,6,7,8]

위 내용은 Python에서 Hill 정렬 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!