배처 홀짝 병합 정렬
보이기
![]() 8개 입력을 받은 홀-짝 병합 정렬망의 시각화 | |
분류 | 정렬 알고리즘 |
---|---|
자료 구조 | 배열 |
최악 시간복잡도 | 병렬 시간 |
최선 시간복잡도 | 병렬 시간 |
평균 시간복잡도 | 병렬 시간 |
공간복잡도 | 비병렬 시간 |
배처 홀짝 병합 정렬(Batcher odd–even mergesort, Batcher's odd–even mergesort[1])은 켄 배처가 크기 O(n (log n)2)와 깊이 O((log n)2)의 정렬망을 위해 고안한 구조이다. 여기서 n은 정렬할 항목의 수이다. 점근적으로 최적화된 것은 아니지만 도널드 커누스는 1998년 AKS 네트워크와 관련하여 "n이 지구상의 모든 컴퓨터의 총 메모리 용적을 초과하지만 않는다면 배처의 방식이 훨씬 더 낫다"고 밝혔다.[2]
그래픽 처리 하드웨어에서 효율적인 정렬을 하는 쉬운 방법으로서 2번째 서적 GPU Gems에 의해 보급되었다.[3]
의사 코드
[편집]# note: the input sequence is indexed from 0 to (n-1)
for p = 1, 2, 4, 8, ... # as long as 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 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)
각주
[편집]- ↑ Batcher, Ken (1968), 《Sorting Networks and their Applications》, AFIPS '68 (Spring), Atlantic City, New Jersey: Association for Computing Machinery, 307–314쪽, doi:10.1145/1468075.1468121, 2020년 10월 24일에 원본 문서에서 보존된 문서
- ↑ D.E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.3.4: Networks for Sorting, pp. 219–247.
- ↑ “Chapter 46. Improved GPU Sorting”.
외부 링크
[편집]- Odd–even mergesort Archived 2019년 12월 22일 - 웨이백 머신 at fh-flensburg.de
- Odd-even mergesort network generator Interactive Batcher's Odd-Even merge-based sorting network generator.