View source for बैचर विषम-सम मर्जसॉर्ट

{{Infobox Algorithm
|class=[[Sorting algorithm]]
|image=[[File:Batcher Odd-Even Mergesort for eight inputs.svg|Visualization of the odd–even mergesort network with eight inputs]]
|caption=Visualization of the odd–even mergesort network with eight inputs
|data=[[Array data structure|Array]]
|best-time= <math>O(\log^2(n))</math> parallel time
|average-time= <math>O(\log^2(n))</math> parallel time
|time=<math>O(\log^2(n))</math> parallel time
|space=<math>O(n\log^2(n))</math> non-parallel time
|optimal=No
}}

बैचर का सम-विषम मर्ज सॉर्ट<ref>
{{Citation
 | 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 (लॉग एन) के नेटवर्क को सॉर्ट करने के लिए [[ क्यों बैच ]] द्वारा तैयार किया गया एक सामान्य निर्माण है<sup>2</sup>) और गहराई O((लॉग एन)<sup>2</sup>), जहां n क्रमबद्ध किए जाने वाले आइटमों की संख्या है। यद्यपि यह स्पर्शोन्मुख रूप से इष्टतम नहीं है, [[डोनाल्ड नुथ]] ने 1998 में सॉर्टिंग नेटवर्क#ऑप्टिमल सॉर्टिंग नेटवर्क के संबंध में निष्कर्ष निकाला कि बैचर की विधि बहुत बेहतर है, जब तक कि एन पृथ्वी पर सभी कंप्यूटरों की कुल मेमोरी क्षमता से अधिक न हो जाए!<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>
इसे दूसरी [[जीपीयू रत्न]] बुक द्वारा लोकप्रिय बनाया गया है,<ref>{{Cite web|url=https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter46.html|title=Chapter 46. Improved GPU Sorting}}</ref> ग्राफ़िक्स-प्रोसेसिंग हार्डवेयर पर यथोचित कुशल सॉर्टिंग करने का एक आसान तरीका।

== स्यूडोकोड ==
तुलना और क्रमबद्ध किए जाने वाले तत्वों के सूचकांकों की गणना करने के लिए विभिन्न पुनरावर्ती और पुनरावृत्तीय योजनाएं संभव हैं। यह n तत्वों को क्रमबद्ध करने के लिए सूचकांक उत्पन्न करने की एक पुनरावृत्तीय तकनीक है:
<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 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)
</syntaxhighlight>
पार्टनर नोड इंडेक्स की गैर-पुनरावर्ती गणना भी संभव है।<ref>{{cite web|url=https://gist.github.com/Bekbolatov/c8e42f5fcaa36db38402|title=Sorting network from Batcher's Odd-Even merge: partner calculation|publisher=Renat Bekbolatov|accessdate=7 May 2015}}</ref>


==यह भी देखें==
* [[बिटोनिक सॉर्टर]]
* [[जोड़ीवार छँटाई नेटवर्क]]

== संदर्भ ==
<references/>


==बाहरी संबंध==
*[http://www.inf.hs-flensburg.de/lang/algorithmen/sortieren/networks/oemen.htm Odd–even mergesort] at hs-flensburg.de
*[https://bekbolatov.github.io/sorting/ Odd-even mergesort network generator] Interactive Batcher's Odd-Even merge-based sorting network generator.

{{sorting}}

{{DEFAULTSORT:Batcher odd-even mergesort}}[[Category: छँटाई एल्गोरिदम]] 



[[Category: Machine Translated Page]]
[[Category:Created On 26/07/2023]]