비토닉 정렬기

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "Bitonic sorter" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2017년 10월) (이 템플릿 메시지 제거 방법과 시기 확인)

비토닉 정렬기

8개의 입력을 가진 비토닉 정렬 네트워크.
클래스	정렬 알고리즘
데이터 구조	배열
최악의 경우 공연	${\displaystyle O(}$ ${\displaystyle {\log }^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}}$(${\displaystyle n}$)${\displaystyle O(\log ^{2}(n)})$ 병렬$$ 시간
베스트 케이스 공연	${\displaystyle O(}$ ${\displaystyle {\log }^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}}$(${\displaystyle n}$)${\displaystyle O(\log ^{2}(n)})$ 병렬$$ 시간
평균 공연	${\displaystyle O(}$ ${\displaystyle {\log }^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}}$(${\displaystyle n}$)${\displaystyle O(\log ^{2}(n)})$ 병렬$$ 시간
최악의 경우 공간 복잡성	${\displaystyle O(n}$ ${\displaystyle {\log }^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}}$( n${\displaystyle }$)${\displaystyle O(n\log ^{2}(n)})$ 비병렬$$ 시간

비토닉 병합은 정렬을 위한 병렬 알고리즘이다.구분망 구축의 공사방식으로도 활용되고 있다.이 알고리즘은 켄 배처가 고안한 것이다.결과 정렬 네트워크는 $O{\displaystyle (n}$ ${\displaystyle {\log }^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle (n}$)${\displaystyle$ O$(n\log ^{2}(n)}$ 대조군으로$$ 구성되며 $O{\displaystyle ({\log }^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle }$ (${\displaystyle n}$)${\$$displaystyle$ O$(\log ^{2}(n)})$의 지연을 가지며$,$ 여기서 $n$은 $정렬$할 항목의$$ 수입니다$.$^[1]

정렬된 시퀀스는 단조롭게 감소하지 않는(또는 증가하지 않는) 시퀀스다.A bitonic sequence is a sequence with ${\displaystyle x_{0}\leq \cdots \leq x_{k}\geq \cdots \geq x_{n-1}}$ for some ${\displaystyle k,0\leq k<n}$, or a circular shift of such a sequence.

복잡성

$Let{\displaystyle }$ p${\displaystyle }$= ${\displaystyle \lfloor }$ ${\displaystyle {\log }_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle n}$ ${\displaystyle \rfloor }$ { $n$⌋ ${\displaystyle p=\lfloor \log$ $\lfloor$ $}$ 및$$ $q{\displaystyle }$= ${\displaystyle \lceil }$ ${\displaystyle {\log }_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ n ⁡ ${\displaystyle n}${ { { { ${$ { { { { q q q q q q q q=\$lceil \{$2}n$\lceil$

병렬 비교의 라운드 수는 $q{\displaystyle }$ (${\displaystyle q}$ +${\displaystyle 1}$) / ${\displaystyle 2\mathrm{}}$ ${\displaystyle q (q+1)/2}$에 의해 주어지는 것이 시공 알고리즘을 통해 명백하다$.$

It follows that the number of comparators ${\displaystyle c}$ is bounded ${\displaystyle 2^{p-1}\cdot p(p+1)/2\leq c\leq \lfloor {n/2}\rfloor \cdot q(q+1)/2}$ (which establishes an exact value for ${\displaystyle c}$ when ${\displaystyle n}$ is a p2의 주전자.

알고리즘의 작동 방식

다음은 16개의 입력을 가진 비토닉 정렬 네트워크다.

16개의 숫자는 왼쪽 끝의 입력으로 입력되고, 16개의 수평선을 따라 미끄러지며, 오른쪽 끝의 출력으로 출력된다.네트워크는 요소들을 분류하기 위해 설계되었으며, 가장 많은 숫자가 하단에 있다.

화살은 대조약이다.두 숫자가 화살표의 양 끝에 도달할 때마다 화살표가 더 큰 숫자를 가리키는지 확인하기 위해 비교한다.만약 그들이 고장났다면, 그들은 교환된다.컬러 박스는 일러스트용일 뿐 알고리즘에는 영향이 없다.

모든 빨간색 상자는 구조가 같다: 상단의 각 입력은 하단의 해당 입력과 비교되며, 모든 화살표가 아래(검은 빨간색) 또는 위(연한 빨간색)를 가리킨다.입력이 비논리적 시퀀스(단일 비삭제 시퀀스에 이어 단일 비증가 시퀀스 또는 그 반대)를 형성하는 경우 출력은 두 개의 비논리적 시퀀스를 형성한다.출력의 상위 절반은 비토닉이 될 것이며, 하위 절반은 비토닉이 될 것이며, 상위 절반의 모든 원소는 하위 절반의 모든 원소(검은 빨강)보다 작거나 같을 것이다(연한 빨강의 경우).이 정리는 명백하지는 않지만, 01 원리를 이용하여 다양한 입력들을 어떻게 비교할 수 있는지에 대한 모든 사례를 주의 깊게 고려함으로써 검증할 수 있다. 여기서 비토닉 시퀀스는 2개 이하의 "10" 또는 "01"을 포함하는 0과 1의 시퀀스다.

빨간 상자들이 합쳐져서 파란색 상자와 초록색 상자들을 형성한다.이러한 모든 상자는 동일한 구조를 가지고 있다: 빨간색 상자는 전체 입력 순서에 적용되고, 그 다음 결과의 각 절반에 적용되며, 그 결과의 각 절반에 적용되며, 기타 등등.모든 화살표는 아래(파란색) 또는 위(녹색)를 가리킨다.이 구조는 나비망으로 알려져 있다.만약 이 박스에 대한 입력이 비토닉적인 경우, 출력은 증가 순서(파란색) 또는 감소 순서(녹색)로 완전히 정렬될 것이다.파란색 또는 녹색 상자에 숫자가 입력되면 첫 번째 빨간색 상자는 목록의 올바른 절반으로 정렬한다.그런 다음, 그것은 그 절반 안에 목록의 정확한 4분의 1로 분류되는 더 작은 빨간 상자를 통과하게 될 것이다.이것은 정확히 정확한 위치로 정리될 때까지 계속된다.따라서 녹색 또는 파란색 상자의 출력은 완전히 정렬될 것이다.

녹색 상자와 파란색 상자는 결합하여 전체 정렬 네트워크를 형성한다.임의의 입력 순서의 경우, 가장 큰 입력 순서가 하단에 있는 입력 순서가 올바르게 정렬된다.각 녹색 또는 파란색 상자의 출력은 정렬된 순서가 될 것이므로, 위쪽은 파란색이고 아래쪽은 녹색이기 때문에 인접 목록의 각 쌍의 출력은 비토닉적일 것이다.파란색과 녹색 상자의 각 열은 N 정렬된 시퀀스를 취하여 쌍으로 결합하여 N/2 비토닉 시퀀스를 형성하고, 그 다음 해당 열의 상자별로 정렬되어 N/2 정렬 시퀀스를 형성한다.이 프로세스는 각 입력을 하나의 요소의 정렬된 목록으로 간주하여 시작하고, 마지막 입력 내용이 하나의 정렬된 목록으로 병합될 때까지 모든 열을 통해 계속된다.마지막 단계가 파란색이었기 때문에, 이 최종 목록은 맨 아래에 가장 큰 요소를 가질 것이다.

대체 표현

위의 다이어그램에서 각 녹색 상자는 파란색 상자와 동일한 작동을 수행하지만, 정렬은 반대 방향으로 수행된다.그래서, 각각의 녹색 상자는 파란색 상자로 교체될 수 있었고, 모든 전선이 반대 위치로 이동하는 교차점이 뒤따를 수 있었다.이렇게 하면 모든 화살표가 같은 방향을 가리키도록 할 수 있지만 수평선이 직선이 되는 것은 막을 수 있다.그러나 유사한 교차점이 어떤 적색 블록에서 나오는 출력물의 하단 절반 오른쪽에 배치될 수 있으며, 비트론 시퀀스의 역방향은 여전히 비트론적이기 때문에 정렬은 여전히 올바르게 작동한다.레드 박스에 전후에 크로스오버가 있으면 내부적으로 다시 배치해 두 크로스오버가 취소돼 와이어가 다시 직선화된다.따라서 다음과 같은 도표는 위의 도표와 같으며, 각 녹색 상자는 청색+크로스오버가 되었고, 각 오렌지 상자는 그러한 두 개의 크로스오버를 흡수한 빨간색 상자로 되어 있다.

모든 대조군은 같은 방향으로 정렬되기 때문에 화살촉이 그려지지 않는다.파란색과 빨간색 블록은 이전과 동일한 작업을 수행한다.주황색 블록은 입력의 하위 절반과 출력 하위 절반에 대해 시퀀스 순서가 역전되는 빨간색 블록과 동일하다.이것은 가장 일반적인 비트 정렬 네트워크의 표현이다.

예시 코드

다음은 C형 유사 부호드로 비토닉 병합에 대한 재귀 없는 구현이다.^[2]

    // 길이가 n인 배열로 지정되면 이 코드는 이를 제자리에 정렬한다.     // 모든 인덱스는 0에서 n-1까지 실행됨     을 위해 (k = 2; k <= n; k *= 2) // k는 반복할 때마다 두 배로 증가한다.         을 위해 (j = k/2; j > 0; j /= 2) // j는 반복할 때마다 반토막이 나며, 부분부분이 잘린다.             을 위해 (i = 0; i < n; i++)                 l = 비트 와이즈XOR (i, j); // C 유사 언어로 "i ^ j" 입니다.                 만일 (l > i)                     만일 (  (비트 와이즈앤드 (i, k) == 0) AND (arr[i] > arr[l])                        OR (비트 와이즈앤드 (i, k) != 0) AND (arr[i] < arr[l]) )                           바꾸다 그 요소들 arr[i] 그리고 arr[l] 

참고 항목

• 배처 홀수-짝수 병합
• 쌍방향 정렬 네트워크

참조

외부 링크

• 이 알고리즘에 대한 논의
• NIST 참조 코드
• 애니메이션 그림 및 작업 코드가 있는 자습서