배처 홀수-짝수 병합

배처 홀수-짝수 병합

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)})$ 비병렬$$ 시간

배쳐의 홀수-짝수 병합은^[1] 켄 배쳐가 O(log n)²와 깊이 O(log n)²의 네트워크를 분류하기 위해 고안한 일반적인 구조로, 여기서 n은 정렬할 항목의 수입니다.증상이 없는 최적의 상태는 아니지만 크누스는 1998년 AKS 네트워크에 대해 "n이 지구상의 모든 컴퓨터의 총 메모리 용량을 초과하지 않는 한 배쳐의 방법이 훨씬 낫다!"^[2]고 결론지었다.

그것은 그래픽 처리 하드웨어에서 상당히 효율적인 분류 작업을 하는 쉬운 방법으로 두 번째 GPU Gems 책에 의해 대중화되었다.^[3]

가성음

비교 및 정렬할 요소의 지수를 계산할 수 있는 다양한 반복적이고 반복적인 계획이 가능하다.이것은 n개의 원소를 분류하기 위한 지수를 생성하기 위한 하나의 반복적 기법이다.

# note: 입력 시퀀스는 p = 1, 2, 4, 8, ...에 대해 0에서 (n-1)까지 색인화된다.# p < n for k = p, p/2, p/4, p/8, ...의 경우.# as long as k >= 1     for j = mod(k,p) to (n-1-k) with a step size of 2k       for i = 0 to min(k-1, n-j-k-1) with a step size of 1         if floor((i+j) / (p*2)) == floor((i+j+k) / (p*2))           compare and sort elements (i+j) and (i+j+k)

파트너 노드 지수의 비반복적인 계산도 가능하다.^[4]

참고 항목

• 비토닉 정렬기
• 쌍방향 정렬 네트워크

참조

외부 링크

• 홀수-짝수 병합 fh-flensburg.de
• 홀수 짝수 병합 네트워크 생성기 대화형 배쳐의 홀수 짝수 병합 기반 정렬 네트워크 생성기