배처 홀짝 병합 정렬

위키백과, 우리 모두의 백과사전.

배처 홀짝 병합 정렬
Visualization of the odd–even mergesort network with eight inputs
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)

각주[편집]

  1. 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일에 원본 문서에서 보존된 문서 
  2. 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.
  3. “Chapter 46. Improved GPU Sorting”. 

외부 링크[편집]