사이클 정렬

이 글에는 여러 가지 문제가 있다. 이 문제를 개선하거나 대화 페이지에서 토의하십시오. (이러한 템플릿 메시지를 제거하는 방법 및 시기 알아보기) 이 글은 일반적인 참고문헌 목록을 포함하고 있지만, 그에 상응하는 인라인 인용구가 충분하지 않기 때문에 대체로 검증되지 않은 상태로 남아 있다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2017년 7월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기) 이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "사이클 분류" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2017년 7월) (이 템플릿 메시지를 제거하는 방법과 시기 학습) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

사이클 정렬

랜덤 번호 목록을 정렬하는 주기 정렬 예제.
클래스	정렬 알고리즘
데이터 구조	배열
최악의 경우 공연	θ(n2)
베스트 케이스 공연	θ(n2)
평균 공연	θ(n2)
최악의 경우 공간 복잡성	θ(n) 합계, θ(1) 보조

사이클 정렬은 다른 인플레이스 정렬 알고리즘과는 달리, 이론적으로 원본 어레이에 대한 총 쓰기 수 측면에서 최적의 비교 정렬 알고리즘이다. 정렬할 순열은 사이클로 인수할 수 있고, 개별적으로 회전해 정렬된 결과를 줄 수 있다는 생각에 근거한다.

거의 모든 종류의 항목과 달리, 항목들은 단순히 그것들을 행동의 방해가 되지 않도록 하기 위해 배열의 다른 곳에 쓰여지지 않는다. 각 값은 이미 올바른 위치에 있는 경우 0번 작성되거나 올바른 위치에 한 번 작성된다. 이는 완료된 인플레이스 정렬에 필요한 최소 덮어쓰기 수와 일치한다.

쓰기 횟수를 최소화하는 것은 플래시 메모리와 같은 EEPROM에서 각 쓰기 작업이 메모리의 수명을 줄이는 것과 같이 매우 비용이 많이 드는 일부 대용량 데이터 세트에 쓰기 작업을 하는 경우에 유용하다.

알고리즘.

사이클 정렬 개념을 설명하려면 구별되는 요소가 있는 목록을 고려하십시오. 요소 $a{\displaystyle }$ ${\$$displaystyle$ $a$$}$을$($를) 지정하면, 전체 목록에서 요소 수를 단순히 $계산$하여 정렬된 목록에서 $발생$할 인덱스를 찾을 수 있다$.$ 이제

1. 요소가 이미 올바른 위치에 있는 경우 아무 작업도 수행하지 마십시오.
2. 그렇지 않다면, 우리는 그것을 의도된 위치에 쓸 것이다. 그 자리에는 다른 원소가 살고 있다. b형이야 그러면위치로 이동해야 한다 올바른 우리는. 요소를 올바른 위치로 교체하는 이 과정은 요소가 a의 원래 위치로 이동될 때까지 계속된다. 이렇게 하면 사이클이 완성된다.

첫 번째 문자 b를 올바른 위치로 이동할 때 목록 "bdeac"의 변위 주기:

모든 요소에 대해 이 프로세스를 반복하면 요소가 이미 올바른 위치에 있지 않은 경우에만 단일 쓰기 작업으로 목록을 정렬한다. 올바른 위치를 계산하는 동안 모든 단일 요소에 $대해{\displaystyle }$ O${\displaystyle }$( n${\displaystyle }$) ${\displaystyle O(n)}$시간이$$ 소요되므로 2차 시간 알고리즘이 생성되므로 쓰기 작업 횟수가 최소화된다.

실행

위의 개요에서 실행 가능한 구현을 만들려면 다음 두 가지 문제를 해결해야 한다.

1. 정확한 위치를 계산할 때, 우리는 사이클의 첫 번째 요소를 이중으로 세지 않도록 해야 한다.
2. 만약 중복된 요소가 존재한다면, 우리는 요소 a를 정확한 위치로 이동시킬 수 있는데, 그것은 이미 a가 거주하고 있는 것이다. 단순히 이것들을 교환하는 것만으로 알고리즘이 무한정 순환하게 될 것이다. 그 대신, 우리는 그 원소의 복제품 뒤에 그 원소를 삽입해야 한다.

다음 Python 구현은^{[1][circular reference]} 어레이에서 사이클 정렬을 수행하며, 이를 정렬하는 데 필요한 어레이에 대한 쓰기 수를 계산한다.

반항하다 cycle_cycle(배열하다) -> 인트로:     ""배열을 제자리에 정렬하고 쓰기 횟수를 반환하십시오."""     글씨를 쓰다 = 0      # 배열을 반복하여 회전할 사이클을 찾으십시오.     을 위해 cycle_start 에 범위(0, 렌(배열하다) - 1):         항목 = 배열하다[cycle_start]          # 물건을 어디에 둘지 찾아라.         양치류 = cycle_start         을 위해 i 에 범위(cycle_start + 1, 렌(배열하다)):             만일 배열하다[i] < 항목:                 양치류 += 1          # 항목이 이미 존재한다면, 이것은 순환이 아니다.         만일 양치류 == cycle_start:             계속하다          # 그렇지 않으면, 물건을 그 곳에 두거나 복제품 바로 뒤에 두어라.         하는 동안에 항목 == 배열하다[양치류]:             양치류 += 1          배열하다[양치류], 항목 = 항목, 배열하다[양치류]         글씨를 쓰다 += 1          # 나머지 사이클을 돌린다.         하는 동안에 양치류 != cycle_start:             # 물건을 어디에 둘지 찾아라.             양치류 = cycle_start             을 위해 i 에 범위(cycle_start + 1, 렌(배열하다)):                 만일 배열하다[i] < 항목:                     양치류 += 1              # 물건을 거기에 두거나 중복된 물건 바로 뒤에 두어라.             하는 동안에 항목 == 배열하다[양치류]:                 양치류 += 1             배열하다[양치류], 항목 = 항목, 배열하다[양치류]             글씨를 쓰다 += 1      돌아오다 글씨를 쓰다 

상황별 최적화

배열에 상대적으로 적은 수의 항목이 중복되어 있을 때, 일정한 시간 완벽한 해시함수는 항목을¹ 어디에 놓을지 찾는 속도를 크게 높일 수 있으며, θ(n²) 시간에서 θ(n + k) 시간(k) 시간(k)은 해시의 총 수입니다. 배열은 결국 해시 순서에 따라 정렬되기 때문에 올바른 순서를 정해 주는 해시함수를 선택하는 것이 중요하다.

정렬하기 전에 배열에서 각 해시의 발생 횟수를 계산하여 해시별로 정렬된 히스토그램을 만드십시오. 그런 다음 히스토그램에서 각 항목의 누적 합계를 사용하여 표를 만드십시오. 누적 합계 표에는 각 원소의 배열의 위치가 포함된다. 요소의 적절한 위치는 선형 검색이 아닌 일정한 시간 해시 및 누적 합계 테이블 조회를 통해 찾을 수 있다.

참조

외부 링크

^ "Cycle-Sort: A Linear Sort Method," The Computer Journal (1990) 33 (4): 365-367.

• 제한되지 않은 변종의 원래 출처
• Cyclesort - 호기심 많은 작은 정렬 알고리즘