छँटाई नेटवर्क

एक साधारण लघुपरिपथ नेटवर्क जिसमें चार तार और पांच संयोजक होते हैं

कंप्यूटर विज्ञान में, लघुपरिपथ नेटवर्क सामान्य उपकरण होते हैं जो तारों की एक निश्चित संख्या से बने होते हैं, आंकिक मानों को जारी रखते हैं, और लघुपरिपथ मॉड्यूल जो तारों के जोड़े को जोड़ते हैं, तारों पर आंकिक मानों की अदला-बदली करते हैं यदि वे वांछित क्रम में नहीं हैं। इस तरह के नेटवर्क सामान्यतः आंकिक मानों की निश्चित संख्या पर वर्गीकरण करने के लिए डिज़ाइन किए जाते हैं, जिस स्थिति में उन्हें श्रेणीकरण नेटवर्क कहा जाता है।

लघुपरिपथ नेटवर्क सामान्य लघुपरिपथ प्रकारों से भिन्न होते हैं, क्योंकि वे अनियंत्रित पद्धति से बड़े इनपुट को संभालने में सक्षम नहीं होते हैं, और इसमें उनकी लघुपरिपथ का क्रम पहले से निर्धारित होता है, चाहे पिछली तुलनाओं के परिणाम कुछ भी हों। बड़ी मात्रा में इनपुट को लघुपरिपथ करने के लिए, नए लघुपरिपथ नेटवर्क का निर्माण किया जाना चाहिए। लघुपरिपथ अनुक्रमों की यह स्वतंत्रता समानांतर निष्पादन और कंप्यूटर हार्डवेयर में कार्यान्वयन के लिए उपयोगी है। लघुपरिपथ जाल की कार्यप्रणाली के अतिरिक्त, उनका सिद्धांत आश्चर्यजनक रूप से गहरा और जटिल है। लघुपरिपथ नेटवर्क का पहली बार अध्ययन आर्मस्ट्रांग, नेल्सन और ओ'कॉनर द्वारा 1954 के आसपास किया गया था,^[1]जिन्होंने बाद में इस विचार का एकीकरण कराया।^[2]

लघुपरिपथ नेटवर्क को या तो कंप्यूटर हार्डवेयर या सॉफ़्टवेयर में लागू किया जा सकता है। डोनाल्ड नुथ बताते हैं कि कैसे द्विआधारी पूर्णांकों के लिए लघुपरिपथ को सरल, त्रि-स्तरीय इलेक्ट्रॉनिक उपकरणों के रूप में कार्यान्वित किया जा सकता है।^[1] क्यून बैच ने 1968 में, बस (कंप्यूटिंग) और तेज़, लेकिन अधिक महंगे, [[क्रॉसबार बदलना ]] दोनों की जगह, कंप्यूटर हार्डवेयर के स्विच बनाने के लिए उनका उपयोग करने का सुझाव दिया।^[3] 2000 के दशक से, लघुपरिपथ नेट (विशेष रूप से बिटोनिक सॉर्टर) ग्राफ़िक्स प्रोसेसिंग युनिट वर्ग समूह पर सामान्य-उद्देश्य चित्रमुद्रण संसाधन एकक पर सामान्य प्रयोजन कंप्यूटिंग चलने के लिए लघुपरिपथ कलन विधि के निर्माण के लिए उपयोग किया जाता है।^[4]

परिचय

लघुपरिपथ नेटवर्क में एक लघुपरिपथ का प्रदर्शन।

एक लघुपरिपथ नेटवर्क में दो प्रकार के वस्तु होते हैं: लघुपरिपथ और तार। तारों को बाएं से दाएं चलने के रूप में माना जाता है, जो एक ही समय में नेटवर्क को पार करने वाले मान (एक प्रति तार) ले जाते हैं। प्रत्येक लघुपरिपथ दो तारों को जोड़ता है। जब आंकिक मानों की एक जोड़ी, तारों की एक जोड़ी के माध्यम से संचरण करते हुए, एक लघुपरिपथ का सामना करती है, तो लघुपरिपथ मानों को स्थानांतरित करता है यदि सिर्फ शीर्ष तार का मान नीचे के तार के आंकिक मान से अधिक या बराबर हो।

सूत्र में, यदि शीर्ष तार $x$ वहन करता है और नीचे का तार $y$ वहन करता है, फिर एक लघुपरिपथ से टकराने के बाद तार $x'=\min(x,y)$ ले जाते हैं और $y'=\max(x,y)$ , क्रमशः, इसलिए मानों की जोड़ी को क्रमबद्ध किया जाता है।^[5]^: 635 तारों को बाएं से दाएं चलने के रूप में माना जाता है, जो एक ही समय में नेटवर्क को पार करने वाले मान (एक प्रति तार) ले जाते हैं। तारों और लघुपरिपथ का एक नेटवर्क जो सभी संभावित इनपुटों को आरोही क्रम में सही ढंग से लघुपरिपथ करेगा, लघुपरिपथ नेटवर्क या क्रुस्कल हब कहलाता है। लघुपरिपथ की तकनीकों को दो श्रेणियों में विभाजित किया जा सकता है। ये हैं: आंतरिक लघुपरिपथ और बाहरी लघुपरिपथ। बाहरी लघुपरिपथ नेटवर्क को प्रतिबिंबित करके, सभी इनपुट को अवरोही क्रम में लघुपरिपथ करना भी संभव है। बड़ी मात्रा में इनपुट को लघुपरिपथ करने के लिए, नए लघुपरिपथ नेटवर्क का निर्माण किया जाना चाहिए।

सरल लघुपरिपथ नेटवर्क का पूरा संचालन नीचे दिखाया गया है। यह स्पष्ट है कि यह लघुपरिपथ नेटवर्क इनपुट को सही ढंग से क्यों लघुपरिपथ करेगा; ध्यान दें कि पहले चार लघुपरिपथ सबसे बड़े मान को नीचे तक निष्क्रिय कर देंगे और सबसे छोटे मान को शीर्ष पर निर्धारित करेंगे। अंतिम लघुपरिपथ मध्य दो तारों को लघुपरिपथ में स्थानांतरित करता है।

गहनता और दक्षता

एक लघुपरिपथ नेटवर्क की दक्षता को उसके कुल आकार से मापा जा सकता है, जिसका अर्थ है कि नेटवर्क में लघुपरिपथ की संख्या, या इसकी गहनता से, तुलनाकर्ताओं की सबसे बड़ी संख्या के रूप में परिभाषित (अनौपचारिक रूप से) जो किसी भी इनपुट आंकिक मान को नेटवर्क के माध्यम से अपने परिपथ मार्ग पर मिल सकता है। यह देखते हुए कि लघुपरिपथ नेटवर्क कुछ लघुपरिपथ समानांतर कंप्यूटिंग कर सकते हैं (एक ही ऊर्ध्वाधर रेखा पर स्थित लघुपरिपथ द्वारा चित्रमय संकेतन में दर्शाया गया है), और इकाई समय लेने के लिए सभी तुलनाओं को मानते हुए, यह देखा जा सकता है कि नेटवर्क की गहनता इसे निष्पादित करने के लिए आवश्यक समय चरणों की संख्या के बराबर है।^[5]^{: 636–637}

निवेशन और बबल नेटवर्क

हम निवेशन और चयन के सिद्धांतों का उपयोग करके आसानी से किसी भी आकार के नेटवर्क का पुनरावर्ती रूप से निर्माण कर सकते हैं। यह मानते हुए कि हमारे पास आकार n का एक लघुपरिपथ नेटवर्क है, हम n + 1 आकार का एक नेटवर्क बना सकते हैं, पहले से लघुपरिपथ किए गए सबनेट में एक अतिरिक्त संख्या डालकर (प्रविष्टि लघुपरिपथ के पीछे के सिद्धांत का उपयोग करके)। हम पहले इनपुट से सबसे कम आंकिक मान का चयन करके और फिर शेष आंकिक मानों को पुनरावर्ती रूप से लघुपरिपथ करके (बबल लघुपरिपथ के सिद्धांत का उपयोग करके) एक ही चीज़ को पूरा कर सकते हैं।).

एक लघुपरिपथ नेटवर्क पुनरावर्ती रूप से निर्मित होता है जो पहले सबसे बड़े मान को नीचे तक ले जाता है और फिर शेष तारों को बबल के आधार पर सॉर्ट करता है।

एक लघुपरिपथ नेटवर्क पुनरावर्ती रूप से निर्मित होता है जो पहले n तारों को सॉर्ट करता है, और फिर शेष मान निवेशन क्रम के आधार पर सम्मिलित करता है।

इन दो लघुपरिपथ नेटवर्कों की संरचना बहुत समान है। दो अलग-अलग रूपांतर का निर्माण, जो एक साथ किए जा सकने वाले लघुपरिपथ को एक साथ निष्क्रिय कर सकता है, यह दर्शाता है कि वास्तव में, वे समान हैं।^[1]

बबल सॉर्टिंग नेटवर्क

निवेशन सॉर्टिंग नेटवर्क

समांतर तुलनित्रों की अनुमति देते समय, बबल सॉर्ट और सम्मिलन सॉर्ट समान होते हैं

निवेशन नेटवर्क (या समतुल्य, बबल नेटवर्क) की गहनता 2n - 3 है, [1] जहां n मानों की संख्या है। यह रैंडम-एक्सेस मशीनों द्वारा आवश्यक O(n log n) समय से बेहतर है, लेकिन यह पता चला है कि केवल O(log2 n) की गहनता वाले अधिक कुशल लघुपरिपथ नेटवर्क हैं, जैसा कि नीचे वर्णित है।

शून्य-एक सिद्धांत

हालांकि कुछ लघुपरिपथ नेटवर्क (जैसे इंसर्शन/बबल सॉर्टर) की वैधता को प्रमाणित करना आसान है, लेकिन यह सदैव इतना आसान नहीं होता है। $n!$ में संख्याओं का क्रमपरिवर्तन $n$ -वायर नेटवर्क, और उन सभी का परीक्षण करने में अत्यधिक समय लगेगा, विशेषकर जब $n$ दीर्घ हो। बड़ी मात्रा में इनपुट को लघुपरिपथ करने के लिए, नए लघुपरिपथ नेटवर्क का निर्माण किया जाना चाहिए। परीक्षण प्रकरणों की संख्या $2 n$ को तथाकथित शून्य-एक सिद्धांत का उपयोग करते हुए अत्यधिक कम किया जा सकता है। जबकि अभी भी यह इससे छोटा घातीय है, $n!$ सभी के लिए $n \geq 4$ , और $n$ अंतर बढ़ने के साथ अत्यधिक तेजी से बढ़ता है।

शून्य-एक सिद्धांत निर्दिष्ट करता है कि, यदि एक लघुपरिपथ नेटवर्क सभी को सही ढंग से लघुपरिपथ कर सकता है, शून्य और एक $2 n$ का अनुक्रम, तो यह अनियंत्रित पद्धति से आदेशित इनपुट के लिए भी मान्य है। यह न केवल नेटवर्क की वैधता का पता लगाने के लिए आवश्यक परीक्षणों की संख्या में भारी कटौती करता है, बल्कि लघुपरिपथ नेटवर्क के कई निर्माणों को बनाने में भी इसका बहुत उपयोग होता है।

सिद्धांत को पहले लघुपरिपथ के बारे में निम्नलिखित तथ्य को देखकर सिद्ध किया जा सकता है: जब एक मोनोटोनिक फलन $f$ कार्य करता है तो वह इनपुट पर लागू होता है, अर्थात, $x$ और $y$ द्वारा प्रतिस्थापित किया जाता है $f (x)$ और $f (y)$ , तो लघुपरिपथ उत्पन्न करता है, $min(f (x), f (y)) = f (min(x, y))$ और $max(f (x), f (y)) = f (max(x, y))$ . नेटवर्क की गहनता पर गणितीय प्रेरण द्वारा, इस परिणाम को लेम्मा (गणित) तक बढ़ाया जा सकता है, जिसमें कहा गया है कि यदि नेटवर्क अनुक्रम को बदल देता है, $a 1, ..., a n$ में $b 1, ..., b n$ , यह बदल जाएगा, मान लीजिए कि $f (a 1), ..., f (a n)$ में $f (b 1), ..., f (b n)$ कुछ इनपुट $a 1, ..., a n$ में दो $a i < a j$ वस्तु हैं, और नेटवर्क असामान्य तरीके से आउटपुट में इनकी अदला-बदली करता है। फिर यह असामान्य तरीके से लघुपरिपथ भी $f (a 1), ..., f (a n)$ फलन के लिए करेगा।

f(x)={\begin{cases}1\ &{\mbox{if }}x>a_{i}\\0\ &{\mbox{otherwise.}}\end{cases}}

यह फलन मोनोटोनिक है, इसलिए हमारे पास प्रतिपरिवर्तित के रूप में शून्य-एक सिद्धांत है।^[5]^{: 640–641}

लघुपरिपथ नेटवर्क का निर्माण

गहनता के लघुपरिपथ नेटवर्क के निर्माण के लिए विभिन्न कलन विधि $O (log 2 n)$ उपस्थित हैं (इसलिए आकार $O (n log 2 n)$ ) जैसे बैचर ऑड-ईवन मर्जसॉर्ट, बिटोनिक प्रकार, शैल लघुपरिपथ और संयुग्मित लघुपरिपथ नेटवर्क। ये नेटवर्क प्रायः व्यवहार में उपयोग किए जाते हैं। बड़ी मात्रा में इनपुट को लघुपरिपथ करने के लिए, नए लघुपरिपथ नेटवर्क का निर्माण किया जाना चाहिए।

गहनता के नेटवर्क $O (log n)$ का निर्माण करना भी संभव है (इसलिए आकार $O (n log n)$ ), एकेएस नेटवर्क नामक एक निर्माण का उपयोग करते हुए, इसके खोजकर्ता मिक्लोस अजताई, जानोस कोमलोस (गणितज्ञ) कोमलोस, और एंड्रे स्ज़ेमेरीडी के नाम पर हुई,^[6] जबकि एक महत्वपूर्ण सैद्धांतिक खोज, बिग-ओ नोटेशन द्वारा छिपे हुए बड़े रैखिक स्थिरांक के कारण एकेएस नेटवर्क के पास बहुत सीमित व्यावहारिक अनुप्रयोग दर्शाता है।^[5]^: 653 ये आंशिक रूप से विस्तारक ग्राफ के निर्माण के कारण हैं।

एकेएस नेटवर्क का एक सरलीकृत संस्करण 1990 में माइकल एस. पैटर्सन द्वारा वर्णित किया गया था, जिन्होंने नोट किया था कि डेप्थ बाउंड के लिए प्राप्त स्थिरांक अभी भी व्यावहारिक आंकिक मान के निर्माण को रोकते हैं।^[7]

एक और हालिया निर्माण को आकार का ज़िग-ज़ैग लघुपरिपथ नेटवर्क कहा जाता है, $O (n log n)$ की खोज माइकल टी. गुडरिच ने 2014 में की थी।^[8] जबकि इसका आकार एकेएस नेटवर्क की लघुपरिपथ में बहुत छोटा है, इसकी गहनता $O (n log n)$ इसे समानांतर कार्यान्वयन के लिए अनुपयुक्त बनाता है।

इष्टतम लघुपरिपथ नेटवर्क

इनपुट की छोटी, निश्चित संख्या के लिए $n$ , न्यूनतम गहनता (अधिकतम समांतर निष्पादन के लिए) या न्यूनतम आकार (लघुपरिपथ की संख्या) के साथ इष्टतम लघुपरिपथ नेटवर्क का निर्माण किया जा सकता है। इन नेटवर्कों का उपयोग बड़े लघुपरिपथ नेटवर्कों के प्रदर्शन को बढ़ाने के लिए किया जा सकता है, जो कलन विधि के निर्माण से उत्पन्न होता है, उदाहरण के लिए, बैचर, रिकर्सन को जल्दी रोककर और बेस केस के रूप में इष्टतम नेट सम्मिलित करके^[9] निम्न तालिका उन छोटे नेटवर्कों के लिए इष्टतमता परिणामों का सार प्रस्तुत करती है जिनके लिए इष्टतम गहनता ज्ञात है:

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
गहनता^[10]	0	1	3	3	5	5	6	6	7	7	8	8	9	9	9	9	10
आकार, ऊपरी सीमा^[11]	0	1	3	5	9	12	16	19	25	29	35	39	45	51	56	60	71
आकार, निचली सीमा (यदि भिन्न हो)^[12]													43	47	51	55	60

बड़े नेटवर्क के लिए वर्तमान में न तो इष्टतम गहनता और न ही इष्टतम आकार ज्ञात है। अब तक ज्ञात सीमाएँ नीचे दी गई तालिका में दी गई हैं:

$n$	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32
गहनता, ऊपरी सीमा^[10]^[13]^[14]	11	11	11	12	12	12	12	13	13	14	14	14	14	14	14
गहनता, निचली सीमा^[10]	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10
आकार, ऊपरी सीमा^[14]	77	85	91	99	107	114	120	131	139	148	155	165	172	180	185
आकार, निचली सीमा^[12]	65	70	75	80	85	90	95	100	105	110	115	120	125	130	135

पहले सोलह गहनता-इष्टतम नेटवर्क नुथ की कंप्यूटर प्रोग्रामिंग की कला में सूचीबद्ध हैं,^[1] और 1973 संस्करण के बाद से हैं; हालाँकि, जबकि पहले आठ की इष्टतमता रॉबर्ट डब्ल्यू फ्लॉयड और नुथ द्वारा 1960 के दशक में स्थापित की गई थी, यह विशेषता 2014 तक अंतिम छह के लिए सिद्ध नहीं हुई थी^[15] (प्रकरण नौ और दस का 1991 में फैसला किया जा चुका है^[9]).

एक से बारह इनपुट के लिए, न्यूनतम (अर्थात आकार-इष्टतम) लघुपरिपथ नेटवर्क ज्ञात हैं, और उच्च आंकिक मानों के लिए, उनके आकार पर कम सीमाएँ $S (n)$ वैन वूरिस के कारण लेम्मा का उपयोग करके आगमनात्मक रूप से प्राप्त किया जा सकता है^[1](पृष्ठ 240): $S (n) \geq S (n - 1) + ⌈log 2 n ⌉$ पहले दस इष्टतम नेटवर्क 1969 के बाद से जाने जाते हैं, पहले आठ को फ़्लॉइड और नुथ के काम के बाद से फिर से इष्टतम के रूप में जाना जाता है, लेकिन प्रकरणों की इष्टतमता $n = 9$ और $n = 10$ को हल करने में 2014 तक का समय लगा।^[11] जिसके लिए सबसे छोटे ज्ञात लघुपरिपथ नेटवर्क की इष्टतमता $n = 11$ और $n = 12$ 2020 में हल किया गया था।^[16]^[1]

उत्पत्ति सम्बन्धी कलन विधि का उपयोग करके इष्टतम लघुपरिपथ नेटवर्क को डिजाइन करने में कुछ काम किया गया है: डी. नुथ ने उल्लेख किया है कि सबसे छोटा ज्ञात लघुपरिपथ नेटवर्क $n = 13$ 1995 में ह्यूग्स जुइल द्वारा उत्पत्ति सम्बन्धी कलन विधि एक विकासवादी प्रक्रिया का अनुकरण करके पाया गया था^[1](पृ. 226), और उसके लिए न्यूनतम गहनता लघुपरिपथ नेटवर्क $n = 9$ और $n = 11$ 2001 में लोरेन श्वीबर्ट द्वारा आनुवंशिक विधियों का उपयोग करते हुए पाए गए थे^[1](पृष्ठ 229)।

लघुपरिपथ नेटवर्क के परीक्षण की जटिलता

जब तक P = NP, परीक्षण की समस्या यह नहीं है कि पदान्वेषी नेटवर्क एक लघुपरिपथ नेटवर्क है, समस्या यह है के co-NP-पूर्ण होने के कारण बड़े आकार के नेटवर्क के लिए निरंतर क्रियाशील बने रहने की संभावना मुश्किल है।^[17]

संदर्भ

↑ ^{Jump up to: 1.0} ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 ^1.7 Knuth, D. E. (1997). The Art of Computer Programming, Volume 3: Sorting and Searching (Second ed.). Addison–Wesley. pp. 219–247. ISBN 978-0-201-89685-5. Section 5.3.4: Networks for Sorting.
↑ US 3029413, O'Connor, Daniel G. & Nelson, Raymond J., "Sorting system with $n$ -line sorting switch", published 10 April 1962
↑ Batcher, K. E. (1968). छँटाई नेटवर्क और उनके अनुप्रयोग. Proc. AFIPS Spring Joint Computer Conference. pp. 307–314.
↑ Owens, J. D.; Houston, M.; Luebke, D.; Green, S.; Stone, J. E.; Phillips, J. C. (2008). "जीपीयू कंप्यूटिंग". Proceedings of the IEEE. 96 (5): 879–899. doi:10.1109/JPROC.2008.917757. S2CID 17091128.
↑ ^{Jump up to: 5.0} ^5.1 ^5.2 ^5.3 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
↑ Ajtai, M.; Komlós, J.; Szemerédi, E. (1983). An $O(n log n)$ sorting network. STOC '83. Proceedings of the fifteenth annual ACM symposium on Theory of computing. pp. 1–9. doi:10.1145/800061.808726. ISBN 0-89791-099-0.
↑ Paterson, M. S. (1990). "Improved sorting networks with $O (log N)$ depth". Algorithmica. 5 (1–4): 75–92. doi:10.1007/BF01840378. S2CID 2064561.
↑ Goodrich, Michael (March 2014). Zig-zag Sort: A Simple Deterministic Data-Oblivious Sorting Algorithm Running in O(n log n) Time. pp. 684–693. arXiv:1403.2777. doi:10.1145/2591796.2591830. ISBN 9781450327107. S2CID 947950. {{cite book}}: |journal= ignored (help)
↑ ^{Jump up to: 9.0} ^9.1 Parberry, Ian (1991). "नाइन-इनपुट सॉर्टिंग नेटवर्क के लिए कंप्यूटर असिस्टेड ऑप्टिमल डेप्थ लोअर बाउंड" (PDF). Mathematical Systems Theory. 24: 101–116. CiteSeerX 10.1.1.712.219. doi:10.1007/bf02090393. S2CID 7077160.
↑ ^{Jump up to: 10.0} ^10.1 ^10.2 Codish, Michael; Cruz-Filipe, Luís; Ehlers, Thorsten; Müller, Mike; Schneider-Kamp, Peter (2015). Sorting Networks: to the End and Back Again. arXiv:1507.01428. Bibcode:2015arXiv150701428C.
↑ ^{Jump up to: 11.0} ^11.1 Codish, Michael; Cruz-Filipe, Luís; Frank, Michael; Schneider-Kamp, Peter (2014). नौ इनपुट (और दस के लिए उनतीस) को छाँटते समय पच्चीस तुलनित्र इष्टतम होते हैं. Proc. Int'l Conf. Tools with AI (ICTAI). pp. 186–193. arXiv:1405.5754. Bibcode:2014arXiv1405.5754C.
↑ ^{Jump up to: 12.0} ^12.1 Obtained by Van Voorhis lemma and the value $S (11) = 35$
↑ Ehlers, Thorsten (February 2017). "Merging almost sorted sequences yields a 24-sorter". Information Processing Letters. 118: 17–20. doi:10.1016/j.ipl.2016.08.005.
↑ ^{Jump up to: 14.0} ^14.1 Dobbelaere, Bert. "SorterHunter". GitHub. Retrieved 2 Jan 2022.
↑ Bundala, D.; Závodný, J. (2014). इष्टतम सॉर्टिंग नेटवर्क. pp. 236–247. arXiv:1310.6271. doi:10.1007/978-3-319-04921-2_19. ISBN 978-3-319-04920-5. S2CID 16860013. {{cite book}}: |journal= ignored (help)
↑ Harder, Jannis (2020). "An Answer to the Bose-Nelson Sorting Problem for 11 and 12 Channels". arXiv:2012.04400 [cs.DS].
↑ Parberry, Ian (1991). इष्टतम सॉर्टिंग नेटवर्क सत्यापन की कम्प्यूटेशनल जटिलता पर. Proc. PARLE '91: Parallel Architectures and Languages Europe, Volume I: Parallel Architectures and Algorithms, Eindhoven, the Netherlands. pp. 252–269.

Angel, O.; Holroyd, A. E.; Romik, D.; Virág, B. (2007). "Random sorting networks". Advances in Mathematics. 215 (2): 839–868. arXiv:math/0609538. doi:10.1016/j.aim.2007.05.019.

बाहरी संबंध

List of smallest sorting networks for given number of inputs
Sorting Networks
CHAPTER 28: SORTING NETWORKS
Sorting Networks
Tool for generating and graphing sorting networks
Sorting networks and the END algorithm
Lipton, Richard J.; Regan, Ken (24 April 2014). "Galactic Sorting Networks". Gödel’s Lost Letter and P=NP.
Sorting Networks validity

[knuth-1] {Jump up to: 1.0} ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 ^1.7 Knuth, D. E. (1997). The Art of Computer Programming, Volume 3: Sorting and Searching (Second ed.). Addison–Wesley. pp. 219–247. ISBN 978-0-201-89685-5. Section 5.3.4: Networks for Sorting.

[2] US 3029413, O'Connor, Daniel G. & Nelson, Raymond J., "Sorting system with $n$ -line sorting switch", published 10 April 1962

[3] Batcher, K. E. (1968). छँटाई नेटवर्क और उनके अनुप्रयोग. Proc. AFIPS Spring Joint Computer Conference. pp. 307–314.

[4] Owens, J. D.; Houston, M.; Luebke, D.; Green, S.; Stone, J. E.; Phillips, J. C. (2008). "जीपीयू कंप्यूटिंग". Proceedings of the IEEE. 96 (5): 879–899. doi:10.1109/JPROC.2008.917757. S2CID 17091128.

[clrs-5] {Jump up to: 5.0} ^5.1 ^5.2 ^5.3 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.

[6] Ajtai, M.; Komlós, J.; Szemerédi, E. (1983). An $O(n log n)$ sorting network. STOC '83. Proceedings of the fifteenth annual ACM symposium on Theory of computing. pp. 1–9. doi:10.1145/800061.808726. ISBN 0-89791-099-0.

[7] Paterson, M. S. (1990). "Improved sorting networks with $O (log N)$ depth". Algorithmica. 5 (1–4): 75–92. doi:10.1007/BF01840378. S2CID 2064561.

[8] Goodrich, Michael (March 2014). Zig-zag Sort: A Simple Deterministic Data-Oblivious Sorting Algorithm Running in O(n log n) Time. pp. 684–693. arXiv:1403.2777. doi:10.1145/2591796.2591830. ISBN 9781450327107. S2CID 947950. {{cite book}}: |journal= ignored (help)

[parberry91-9] {Jump up to: 9.0} ^9.1 Parberry, Ian (1991). "नाइन-इनपुट सॉर्टिंग नेटवर्क के लिए कंप्यूटर असिस्टेड ऑप्टिमल डेप्थ लोअर बाउंड" (PDF). Mathematical Systems Theory. 24: 101–116. CiteSeerX 10.1.1.712.219. doi:10.1007/bf02090393. S2CID 7077160.

[codish_end_game-10] {Jump up to: 10.0} ^10.1 ^10.2 Codish, Michael; Cruz-Filipe, Luís; Ehlers, Thorsten; Müller, Mike; Schneider-Kamp, Peter (2015). Sorting Networks: to the End and Back Again. arXiv:1507.01428. Bibcode:2015arXiv150701428C.

[codish-11] {Jump up to: 11.0} ^11.1 Codish, Michael; Cruz-Filipe, Luís; Frank, Michael; Schneider-Kamp, Peter (2014). नौ इनपुट (और दस के लिए उनतीस) को छाँटते समय पच्चीस तुलनित्र इष्टतम होते हैं. Proc. Int'l Conf. Tools with AI (ICTAI). pp. 186–193. arXiv:1405.5754. Bibcode:2014arXiv1405.5754C.

[vvoorhis-12] {Jump up to: 12.0} ^12.1 Obtained by Van Voorhis lemma and the value $S (11) = 35$

[13] Ehlers, Thorsten (February 2017). "Merging almost sorted sequences yields a 24-sorter". Information Processing Letters. 118: 17–20. doi:10.1016/j.ipl.2016.08.005.

[sorterhunter-14] {Jump up to: 14.0} ^14.1 Dobbelaere, Bert. "SorterHunter". GitHub. Retrieved 2 Jan 2022.

[bundala_zavodny-15] Bundala, D.; Závodný, J. (2014). इष्टतम सॉर्टिंग नेटवर्क. pp. 236–247. arXiv:1310.6271. doi:10.1007/978-3-319-04921-2_19. ISBN 978-3-319-04920-5. S2CID 16860013. {{cite book}}: |journal= ignored (help)

[harder-16] Harder, Jannis (2020). "An Answer to the Bose-Nelson Sorting Problem for 11 and 12 Channels". arXiv:2012.04400 [cs.DS].

[parberry-17] Parberry, Ian (1991). इष्टतम सॉर्टिंग नेटवर्क सत्यापन की कम्प्यूटेशनल जटिलता पर. Proc. PARLE '91: Parallel Architectures and Languages Europe, Volume I: Parallel Architectures and Algorithms, Eindhoven, the Netherlands. pp. 252–269.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

Anonymous

Search

छँटाई नेटवर्क

Namespaces

More

Page actions

Contents