बैचर विषम-सम मर्जसॉर्ट
 Visualization of the odd–even mergesort network with eight inputs | |
| Class | Sorting algorithm |
|---|---|
| Data structure | Array |
| Worst-case performance | parallel time |
| Best-case performance | parallel time |
| Average performance | parallel time |
| Worst-case space complexity | non-parallel time |
बैचर का सम-विषम मर्ज सॉर्ट[1]आकार O(n (log n)2) के नेटवर्क को सॉर्ट करने के लिए केन बैचर द्वारा तैयार किया गया सामान्य निर्माण है) जहां n क्रमबद्ध किए जाने वाले आइटमों की संख्या है। यद्यपि यह स्पर्शोन्मुख रूप से इष्टतम नहीं है, डोनाल्ड नुथ ने 1998 में सॉर्टिंग नेटवर्क ऑप्टिमल सॉर्टिंग नेटवर्क के संबंध में निष्कर्ष निकाला कि बैचर की विधि अधिक उत्तम है, जब तक कि n एअर्थ पर सभी कंप्यूटरों की कुल मेमोरी क्षमता से अधिक न हो जाए![2]
इसे दूसरी जीपीयू जेम्स बुक द्वारा लोकप्रिय बनाया गया है,[3] ग्राफिक्स-प्रोसेसिंग हार्डवेयर पर उचित रूप से कुशल सॉर्ट करने की सरल विधि है।
स्यूडोकोड
तुलना और क्रमबद्ध किए जाने वाले एलिमेंट्स के सूचकांकों की गणना करने के लिए विभिन्न पुनरावर्ती और पुनरावृत्तीय योजनाएं संभव हैं। यह n एलिमेंट्स को क्रमबद्ध करने के लिए सूचकांक उत्पन्न करने की पुनरावृत्तीय तकनीक है:
# 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)
पार्टनर नोड इंडेक्स की गैर-पुनरावर्ती गणना भी संभव है।[4]
यह भी देखें
संदर्भ
- ↑ Batcher, Ken (1968), Sorting Networks and their Applications, AFIPS '68 (Spring), Atlantic City, New Jersey: Association for Computing Machinery, pp. 307–314, doi:10.1145/1468075.1468121, archived from the original on 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".
- ↑ "Sorting network from Batcher's Odd-Even merge: partner calculation". Renat Bekbolatov. Retrieved 7 May 2015.
बाहरी संबंध
- Odd–even mergesort at hs-flensburg.de
- Odd-even mergesort network generator Interactive Batcher's Odd-Even merge-based sorting network generator.
