힐 시퀀싱의 사상

힐 정렬 알고리즘 사상: 힐 정렬은 아래 첨자 증분에 따라 그룹화되고, 각 그룹에 삽입 정렬 알고리즘을 사용하여 정렬되며, 증분이 감소함에 따라 각 그룹에 포함된 키워드가 점점 많아지고, 증분이 1 로 줄어들면 전체 시퀀스가 그룹화되고 알고리즘이 종료됩니다.

예를 들어, 힐 정렬의 기본 단계를 살펴보겠습니다. 초기 증분 GAP = 길이/2 를 선택하고, 감소 증분은 증분 gap=1 이 될 때까지 계속 gap=gap/2 로 진행됩니다. 증분의 각 변형은 원래 시퀀스를 그룹으로 나누어 각 그룹을 개별적으로 삽입합니다.

매번 증분 구분 그룹을 통해 삽입 정렬 거시적으로 작은 숫자가 앞쪽으로 이동하고 큰 숫자가 뒤쪽으로 이동하며 마지막 증분 gap=1 이 삽입 정렬을 수행한 후 최종 순서가 됩니다.

여러 번 삽입된 정렬로 인해 한 번 삽입된 정렬이 안정적이라는 것을 알고 있습니다. 같은 요소의 상대 순서는 변경되지 않지만, 서로 다른 삽입 정렬 과정에서 같은 요소가 각각의 삽입 정렬에서 이동할 수 있으며, 결국 안정성이 깨질 수 있으므로 셸 정렬이 불안정합니다.

발전 내역

힐 정렬은 1959 년 힐이 발표한 논문인 "A high-speed sorting procedure" 에 설명된 디자이너 힐 (Donald Shell) 의 이름을 따서 명명되었습니다.

1961 년 IBM 의 여성 프로그래머 Marlene Metzner Norton 이 처음으로 FORTRAN 언어 프로그래밍을 사용하여 힐 정렬 알고리즘을 구현했습니다. 프로그램에서 힐 정렬에 필요한 증분 시퀀스를 설정하는 간단하고 효과적인 방법을 사용했습니다. 첫 번째 증분은 정렬할 레코드 수의 절반을 가져온 다음 한 번에 반으로 반으로 절반으로, 마지막 증분은 1 입니다.

나중에 Shell-Metzner 알고리즘으로 불리게 된 이 알고리즘은 2003 년 한 이메일에서 "저는 이런 알고리즘을 위해 아무것도 하지 않았습니다. 제 이름은 알고리즘의 이름에 나타나지 않아야 합니다." 라고 말했습니다. "