배처 홀짝 병합 정렬 문서 원본 보기

{{위키데이터 속성 추적}}
{{Infobox Algorithm
|class=[[정렬 알고리즘]]
|image=[[파일:Batcher Odd-Even Mergesort for eight inputs.svg|Visualization of the odd–even mergesort network with eight inputs]]
|caption=8개 입력을 받은 홀-짝 병합 정렬망의 시각화
|data=[[배열]]
|best-time= <math>O(\log^2(n))</math> 병렬 시간
|average-time= <math>O(\log^2(n))</math> 병렬 시간
|time=<math>O(\log^2(n))</math> 병렬 시간
|space=<math>O(n\log^2(n))</math> 비병렬 시간
|optimal=아니오
}}
'''배처 홀짝 병합 정렬'''(Batcher odd–even mergesort, Batcher's odd–even mergesort<ref>
{{인용
 | last=Batcher
 | first=Ken
 | author-link =Ken Batcher
 | title =Sorting Networks and their Applications
 | place =Atlantic City, New Jersey
 | publisher =Association for Computing Machinery
 | pages =307–314
 | year =1968
 | url =http://www.cs.kent.edu/~batcher/sort.ps
 | archive-url=https://web.archive.org/web/20201024081257/http://www.cs.kent.edu/~batcher/sort.ps
 | archive-date=2020-10-24
 | url-status=live
 | doi =10.1145/1468075.1468121
 | series =AFIPS '68 (Spring)}}</ref>)은 [[켄 배처]]가 크기 O(''n''&nbsp;(log&nbsp;''n'')<sup>2</sup>)와 깊이 O((log&nbsp;''n'')<sup>2</sup>)의 [[정렬망]]을 위해 고안한 구조이다. 여기서 n은 정렬할 항목의 수이다. 점근적으로 최적화된 것은 아니지만 [[도널드 커누스]]는 1998년 [[AKS 네트워크]]와 관련하여 "n이 지구상의 모든 컴퓨터의 총 메모리 용적을 초과하지만 않는다면 배처의 방식이 훨씬 더 낫다"고 밝혔다.<ref>[[Donald Knuth|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&ndash;247.</ref>

그래픽 처리 하드웨어에서 효율적인 정렬을 하는 쉬운 방법으로서 2번째 서적 GPU Gems에 의해 보급되었다.<ref>{{웹 인용|url=https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter46.html|title=Chapter 46. Improved GPU Sorting}}</ref>

== 의사 코드 ==
<syntaxhighlight lang="text">
# 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)
</syntaxhighlight>

== 각주 ==
{{각주}}

== 외부 링크 ==
* [http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/oemen.htm Odd–even mergesort] {{웹아카이브|url=https://web.archive.org/web/20191222122424/http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/oemen.htm}} at fh-flensburg.de
* [https://bekbolatov.github.io/sorting/ Odd-even mergesort network generator] Interactive Batcher's Odd-Even merge-based sorting network generator.

{{정렬 알고리즘}}

[[분류:정렬 알고리즘]]