순환 파티션: 최대 1.5배 빠른 파티션 알고리즘

시퀀스 파티셔닝(Sequence partitioning)은 컴퓨터 프로그래밍의 기본 알고리즘으로, 피벗 값을 기반으로 시퀀스의 숫자를 재정렬합니다. 목표는 피벗 값보다 작은 모든 숫자를 먼저 배치한 다음 나머지 숫자를 배치하는 것입니다. QuickSort 및 시퀀스의 중앙값 찾기를 포함하여 파티셔닝의 다양한 응용 프로그램이 있습니다. 현재 잘 알려진 두 가지 분할 알고리즘이 있습니다: Lomuto 체계와 Hoare 체계. Hoare 체계는 배열 내부에서 더 적은 재배열을 수행하기 때문에 실제로 선호되는 경우가 많습니다. "순환 파티션"이라는 새로운 파티션 스키마가 제안되었는데, 이는 Hoare 스키마와 유사하지만 1.5배 더 적은 재배열을 수행합니다. 순환 분할 체계는 값 할당의 수가 처음에 해당 위치에 있지 않은 값의 수와 거의 같아지기 때문에 거의 최적의 것으로 간주됩니다. Hoare 체계가 검토되고 두 스캔이 서로 만나는 위치에 관계없이 시간 복잡도는 O(N)입니다. Hoare 체계에는 3L/2 할당이 필요하며, 여기서 L은 해당 위치에 없는 값의 수입니다. 할당 주기의 개념이 도입되었으며, 이는 Hoare 분할 체계를 최적화하는 데 필요합니다. 순환 왼쪽 시프트 및 시퀀스 반전을 포함하여 다양한 재배열 사례가 제시되어 일부 재배열에 다른 재배열보다 더 많은 할당이 필요하다는 것을 보여줍니다.