लघुपरिपथ नेटवर्क: Difference between revisions

Latest revision as of 15:27, 19 April 2023

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

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

लघुपरिपथ नेटवर्क सामान्य लघुपरिपथ प्रकारों से भिन्न होते हैं, क्योंकि वे अनियंत्रित पद्धति से बड़े इनपुट को संभालने में सक्षम नहीं होते हैं, और इसमें उनकी लघुपरिपथ का क्रम पहले से निर्धारित होता है, चाहे पिछली तुलनाओं के परिणाम कुछ भी हों। बड़ी मात्रा में इनपुट को लघुपरिपथ करने के लिए, नए लघुपरिपथ नेटवर्क का निर्माण किया जाना चाहिए। लघुपरिपथ अनुक्रमों की यह स्वतंत्रता समानांतर निष्पादन और कंप्यूटर हार्डवेयर में कार्यान्वयन के लिए उपयोगी है। लघुपरिपथ जाल की कार्यप्रणाली के अतिरिक्त, उनका सिद्धांत आश्चर्यजनक रूप से गहरा और जटिल है। लघुपरिपथ नेटवर्क का पहली बार अध्ययन आर्मस्ट्रांग, नेल्सन और ओ'कॉनर द्वारा 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]

संदर्भ

↑ ^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.
↑ ^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)
↑ ^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.
↑ ^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.
↑ ^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.
↑ ^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.
↑ ^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] 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] 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] 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] 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] 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] 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] 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]

@@ Line 1: / Line 1: @@
-[[File:SimpleSortingNetwork2.svg|thumb|300px|एक साधारण वर्गीकरण नेटवर्क जिसमें चार तार और पांच कनेक्टर होते हैं]][[कंप्यूटर विज्ञान]] में, तुलनाकारी नेटवर्क सामान्य उपकरण होते हैं जो तारों की एक निश्चित संख्या से बने होते हैं, मूल्यों को जारी रखते हैं, और तुलनाकारी मॉड्यूल जो तारों के जोड़े को जोड़ते हैं, तारों पर मूल्यों की अदला-बदली करते हैं यदि वे वांछित क्रम में नहीं हैं। इस तरह के नेटवर्क सामान्यतः  मूल्यों की निश्चित संख्या पर [[छँटाई एल्गोरिथ्म|वर्गीकरण]] करने के लिए डिज़ाइन किए जाते हैं, जिस स्थिति में उन्हें श्रेणीकरण नेटवर्क कहा जाता है।
+[[File:SimpleSortingNetwork2.svg|thumb|300px|एक साधारण लघुपरिपथ नेटवर्क जिसमें चार तार और पांच संयोजक होते हैं]][[कंप्यूटर विज्ञान]] में, लघुपरिपथ नेटवर्क सामान्य उपकरण होते हैं जो तारों की एक निश्चित संख्या से बने होते हैं, आंकिक मानों को जारी रखते हैं, और लघुपरिपथ मॉड्यूल जो तारों के जोड़े को जोड़ते हैं, तारों पर आंकिक मानों की अदला-बदली करते हैं यदि वे वांछित क्रम में नहीं हैं। इस तरह के नेटवर्क सामान्यतः आंकिक मानों की निश्चित संख्या पर [[छँटाई एल्गोरिथ्म|वर्गीकरण]] करने के लिए डिज़ाइन किए जाते हैं, जिस स्थिति में उन्हें श्रेणीकरण नेटवर्क कहा जाता है।
-वर्गीकरण नेटवर्क सामान्य तुलना प्रकारों से भिन्न होते हैं, क्योंकि वे मनमाने ढंग से बड़े इनपुट को संभालने में सक्षम नहीं होते हैं, और इसमें उनकी तुलना का क्रम पहले से निर्धारित होता है, चाहे पिछली तुलनाओं के परिणाम कुछ भी हों। बड़ी मात्रा में इनपुट को वर्गीकरण करने के लिए, नए वर्गीकरण नेटवर्क का निर्माण किया जाना चाहिए। तुलना अनुक्रमों की यह स्वतंत्रता समानांतर निष्पादन और [[कंप्यूटर हार्डवेयर]] में कार्यान्वयन के लिए उपयोगी है। वर्गीकरण  जाल की सादगी के अतिरिक्त , उनका सिद्धांत आश्चर्यजनक रूप से गहरा और जटिल है। वर्गीकरण  नेटवर्क का पहली बार अध्ययन आर्मस्ट्रांग, नेल्सन और ओ'कॉनर द्वारा 1954 के आसपास किया गया था,<ref name="knuth"/>जिन्होंने बाद में इस विचार का एकस्वित कराया।<ref>{{cite patent |country=US |number=3029413 |title=Sorting system with {{mvar|n}}-line sorting switch |pubdate=10 April 1962 |fdate= 21 February 1957 |inventor1-first=Daniel G. |inventor1-last=O'Connor |inventor2-first=Raymond J. |inventor2-last=Nelson}}</ref>
+लघुपरिपथ नेटवर्क सामान्य लघुपरिपथ प्रकारों से भिन्न होते हैं, क्योंकि वे अनियंत्रित पद्धति से बड़े इनपुट को संभालने में सक्षम नहीं होते हैं, और इसमें उनकी लघुपरिपथ का क्रम पहले से निर्धारित होता है, चाहे पिछली तुलनाओं के परिणाम कुछ भी हों। बड़ी मात्रा में इनपुट को लघुपरिपथ करने के लिए, नए लघुपरिपथ नेटवर्क का निर्माण किया जाना चाहिए। लघुपरिपथ अनुक्रमों की यह स्वतंत्रता समानांतर निष्पादन और [[कंप्यूटर हार्डवेयर]] में कार्यान्वयन के लिए उपयोगी है। लघुपरिपथ जाल की कार्यप्रणाली के अतिरिक्त, उनका सिद्धांत आश्चर्यजनक रूप से गहरा और जटिल है। लघुपरिपथ नेटवर्क का पहली बार अध्ययन आर्मस्ट्रांग, नेल्सन और ओ'कॉनर द्वारा 1954 के आसपास किया गया था,<ref name="knuth"/>जिन्होंने बाद में इस विचार का एकीकरण कराया।<ref>{{cite patent |country=US |number=3029413 |title=Sorting system with {{mvar|n}}-line sorting switch |pubdate=10 April 1962 |fdate= 21 February 1957 |inventor1-first=Daniel G. |inventor1-last=O'Connor |inventor2-first=Raymond J. |inventor2-last=Nelson}}</ref>
-वर्गीकरण नेटवर्क को या तो कंप्यूटर हार्डवेयर या [[ सॉफ़्टवेयर |सॉफ़्टवेयर]] में लागू किया जा सकता है। [[डोनाल्ड नुथ]] बताते हैं कि कैसे द्विआधारी पूर्णांकों के लिए तुलनित्रों को सरल, तीन-राज्य इलेक्ट्रॉनिक उपकरणों के रूप में कार्यान्वित किया जा सकता है।<ref name="knuth" />[[ क्यों बैच | क्यों बैच]] ने 1968 में, [[बस (कंप्यूटिंग)]] और तेज़, लेकिन अधिक महंगे, [[क्रॉसबार [[ बदलना | बदलना]] ]] दोनों की जगह, कंप्यूटर हार्डवेयर के लिए स्विच बनाने के लिए उनका उपयोग करने का सुझाव दिया।<ref>{{cite conference |first=K. E. |last=Batcher |url=http://www.cs.kent.edu/~batcher/sort.ps |title=छँटाई नेटवर्क और उनके अनुप्रयोग|conference=Proc. AFIPS Spring Joint Computer Conference |pages=307–314 |year=1968}}</ref> 2000 के दशक से, वर्गीकरण नेट (विशेष रूप से [[बिटोनिक सॉर्टर]]) [[ ग्राफ़िक्स प्रोसेसिंग युनिट | ग्राफ़िक्स प्रोसेसिंग युनिट]] समुदाय पर सामान्य-उद्देश्य [[ग्राफिक्स प्रोसेसिंग यूनिट पर सामान्य प्रयोजन कंप्यूटिंग|चित्रमुद्रणसंसाधन एकक पर सामान्य प्रयोजन कंप्यूटिंग]] चलने के लिए वर्गीकरण एल्गोरिदम के निर्माण के लिए उपयोग किया जाता है।<ref>{{Cite journal | doi = 10.1109/JPROC.2008.917757| title = जीपीयू कंप्यूटिंग| journal = Proceedings of the IEEE| volume = 96| issue = 5| pages = 879–899| year = 2008| last1 = Owens | first1 = J. D. | last2 = Houston | first2 = M.| last3 = Luebke | first3 = D.| last4 = Green | first4 = S.| last5 = Stone | first5 = J. E. | last6 = Phillips | first6 = J. C. | s2cid = 17091128}}</ref>
+लघुपरिपथ नेटवर्क को या तो कंप्यूटर हार्डवेयर या [[ सॉफ़्टवेयर |सॉफ़्टवेयर]] में लागू किया जा सकता है। [[डोनाल्ड नुथ]] बताते हैं कि कैसे द्विआधारी पूर्णांकों के लिए लघुपरिपथ को सरल, त्रि-स्तरीय इलेक्ट्रॉनिक उपकरणों के रूप में कार्यान्वित किया जा सकता है।<ref name="knuth" /> [[ क्यों बैच |क्यून बैच]] ने 1968 में, [[बस (कंप्यूटिंग)]] और तेज़, लेकिन अधिक महंगे, [[क्रॉसबार [[ बदलना |बदलना]] ]] दोनों की जगह, कंप्यूटर हार्डवेयर के स्विच बनाने के लिए उनका उपयोग करने का सुझाव दिया।<ref>{{cite conference |first=K. E. |last=Batcher |url=http://www.cs.kent.edu/~batcher/sort.ps |title=छँटाई नेटवर्क और उनके अनुप्रयोग|conference=Proc. AFIPS Spring Joint Computer Conference |pages=307–314 |year=1968}}</ref> 2000 के दशक से, लघुपरिपथ नेट (विशेष रूप से [[बिटोनिक सॉर्टर]]) [[ ग्राफ़िक्स प्रोसेसिंग युनिट |ग्राफ़िक्स प्रोसेसिंग युनिट]] वर्ग समूह पर सामान्य-उद्देश्य [[ग्राफिक्स प्रोसेसिंग यूनिट पर सामान्य प्रयोजन कंप्यूटिंग|चित्रमुद्रण संसाधन एकक पर सामान्य प्रयोजन कंप्यूटिंग]] चलने के लिए लघुपरिपथ कलन विधि के निर्माण के लिए उपयोग किया जाता है।<ref>{{Cite journal | doi = 10.1109/JPROC.2008.917757| title = जीपीयू कंप्यूटिंग| journal = Proceedings of the IEEE| volume = 96| issue = 5| pages = 879–899| year = 2008| last1 = Owens | first1 = J. D. | last2 = Houston | first2 = M.| last3 = Luebke | first3 = D.| last4 = Green | first4 = S.| last5 = Stone | first5 = J. E. | last6 = Phillips | first6 = J. C. | s2cid = 17091128}}</ref>
 == परिचय ==
-[[File:Sorting-network-comparator-demonstration.svg|thumb|150px|वर्गीकरण नेटवर्क में एक तुलनाकारी का प्रदर्शन।]]एक वर्गीकरण नेटवर्क में दो प्रकार के वस्तु होते हैं: तुलनाकारी और तार। तारों को बाएं से दाएं चलने के रूप में माना जाता है, जो एक ही समय में नेटवर्क को पार करने वाले मान (एक प्रति तार) ले जाते हैं। प्रत्येक तुलनाकारी दो तारों को जोड़ता है। जब मूल्यों की एक जोड़ी, तारों की एक जोड़ी के माध्यम से यात्रा करते हुए, एक तुलनाकारी का सामना करती है, तो तुलनाकारी मानों को हेरा फेरी करता है यदि और केवल अगर शीर्ष तार का मान नीचे के तार के मूल्य से अधिक या बराबर हो।
+[[File:Sorting-network-comparator-demonstration.svg|thumb|150px|लघुपरिपथ नेटवर्क में एक लघुपरिपथ का प्रदर्शन।]]एक लघुपरिपथ नेटवर्क में दो प्रकार के वस्तु होते हैं: लघुपरिपथ और तार। तारों को बाएं से दाएं चलने के रूप में माना जाता है, जो एक ही समय में नेटवर्क को पार करने वाले मान (एक प्रति तार) ले जाते हैं। प्रत्येक लघुपरिपथ दो तारों को जोड़ता है। जब आंकिक मानों की एक जोड़ी, तारों की एक जोड़ी के माध्यम से संचरण करते हुए, एक लघुपरिपथ का सामना करती है, तो लघुपरिपथ मानों को स्थानांतरित करता है यदि सिर्फ शीर्ष तार का मान नीचे के तार के आंकिक मान से अधिक या बराबर हो।
-सूत्र में, यदि शीर्ष तार वहन करता है {{mvar|x}} और नीचे का तार वहन करता है {{mvar|y}}, फिर एक तुलनाकारी से टकराने के बाद तार ले जाते हैं <math>x' = \min(x, y)</math> और <math>y' = \max(x, y)</math>, क्रमशः, इसलिए मानों की जोड़ी को क्रमबद्ध किया जाता है।<ref name="clrs">{{Introduction to Algorithms|1}}</ref>{{rp|635}} तारों को बाएं से दाएं चलने के रूप में माना जाता है, जो एक ही समय में नेटवर्क को पार करने वाले मान (एक प्रति तार) ले जाते हैं। तारों और तुलनित्रों का एक नेटवर्क जो सभी संभावित इनपुटों को आरोही क्रम में सही ढंग से वर्गीकरण करेगा, वर्गीकरण नेटवर्क या क्रुस्कल हब कहलाता है। नेटवर्क को प्रतिबिंबित करके, सभी इनपुट को अवरोही क्रम में वर्गीकरण करना भी संभव है।
+सूत्र में, यदि शीर्ष तार {{mvar|x}} वहन करता है और नीचे का तार {{mvar|y}} वहन करता है, फिर एक लघुपरिपथ से टकराने के बाद तार <math>x' = \min(x, y)</math> ले जाते हैं और <math>y' = \max(x, y)</math>, क्रमशः, इसलिए मानों की जोड़ी को क्रमबद्ध किया जाता है।<ref name="clrs">{{Introduction to Algorithms|1}}</ref>{{rp|635}} तारों को बाएं से दाएं चलने के रूप में माना जाता है, जो एक ही समय में नेटवर्क को पार करने वाले मान (एक प्रति तार) ले जाते हैं। तारों और लघुपरिपथ का एक नेटवर्क जो सभी संभावित इनपुटों को आरोही क्रम में सही ढंग से लघुपरिपथ करेगा, लघुपरिपथ नेटवर्क या क्रुस्कल हब कहलाता है। लघुपरिपथ की तकनीकों को दो श्रेणियों में विभाजित किया जा सकता है। ये हैं: आंतरिक लघुपरिपथ और बाहरी लघुपरिपथ। बाहरी लघुपरिपथ नेटवर्क को प्रतिबिंबित करके, सभी इनपुट को अवरोही क्रम में लघुपरिपथ करना भी संभव है। बड़ी मात्रा में इनपुट को लघुपरिपथ करने के लिए, नए लघुपरिपथ नेटवर्क का निर्माण किया जाना चाहिए।
-सरल वर्गीकरण  नेटवर्क का पूरा संचालन नीचे दिखाया गया है। यह स्पष्ट है कि यह वर्गीकरण नेटवर्क इनपुट को सही ढंग से क्यों वर्गीकरण करेगा; ध्यान दें कि पहले चार तुलनाकारी सबसे बड़े मान को नीचे तक डुबो देंगे और सबसे छोटे मान को शीर्ष पर फ़्लोट करेंगे। अंतिम तुलनाकारी मध्य दो तारों को छाँटता है।
+सरल लघुपरिपथ नेटवर्क का पूरा संचालन नीचे दिखाया गया है। यह स्पष्ट है कि यह लघुपरिपथ नेटवर्क इनपुट को सही ढंग से क्यों लघुपरिपथ करेगा; ध्यान दें कि पहले चार लघुपरिपथ सबसे बड़े मान को नीचे तक निष्क्रिय कर देंगे और सबसे छोटे मान को शीर्ष पर निर्धारित करेंगे। अंतिम लघुपरिपथ मध्य दो तारों को लघुपरिपथ में स्थानांतरित करता है।
 [[File:SimpleSortingNetworkFullOperation.svg|650px]]
-=== गहराई और दक्षता ===
+=== गहनता और दक्षता ===
-एक वर्गीकरण  नेटवर्क की दक्षता को उसके कुल आकार से मापा जा सकता है, जिसका अर्थ है कि नेटवर्क में तुलनित्रों की संख्या, या इसकी गहराई से, तुलनाकर्ताओं की सबसे बड़ी संख्या के रूप में परिभाषित (अनौपचारिक रूप से) जो किसी भी इनपुट मूल्य को नेटवर्क के माध्यम से अपने रास्ते पर मिल सकता है। . यह देखते हुए कि वर्गीकरण  नेटवर्क कुछ तुलना [[समानांतर कंप्यूटिंग]] कर सकते हैं (एक ही ऊर्ध्वाधर रेखा पर स्थित तुलनित्रों द्वारा चित्रमय संकेतन में दर्शाया गया है), और इकाई समय लेने के लिए सभी तुलनाओं को मानते हुए, यह देखा जा सकता है कि नेटवर्क की गहराई के बराबर है इसे निष्पादित करने के लिए आवश्यक समय चरणों की संख्या।<ref name="clrs"/>{{rp|636–637}}
+एक लघुपरिपथ नेटवर्क की दक्षता को उसके कुल आकार से मापा जा सकता है, जिसका अर्थ है कि नेटवर्क में लघुपरिपथ की संख्या, या इसकी गहनता से, तुलनाकर्ताओं की सबसे बड़ी संख्या के रूप में परिभाषित (अनौपचारिक रूप से) जो किसी भी इनपुट आंकिक मान को नेटवर्क के माध्यम से अपने परिपथ मार्ग पर मिल सकता है। यह देखते हुए कि लघुपरिपथ नेटवर्क कुछ लघुपरिपथ [[समानांतर कंप्यूटिंग]] कर सकते हैं (एक ही ऊर्ध्वाधर रेखा पर स्थित लघुपरिपथ द्वारा चित्रमय संकेतन में दर्शाया गया है), और इकाई समय लेने के लिए सभी तुलनाओं को मानते हुए, यह देखा जा सकता है कि नेटवर्क की गहनता इसे निष्पादित करने के लिए आवश्यक समय चरणों की संख्या के बराबर है।<ref name="clrs"/>{{rp|636–637}}
-=== सम्मिलन और बुलबुला नेटवर्क ===
+=== निवेशन और बबल नेटवर्क ===
-हम सम्मिलन और चयन के सिद्धांतों का उपयोग करके आसानी से किसी भी आकार के नेटवर्क का पुनरावर्ती रूप से निर्माण कर सकते हैं। यह मानते हुए कि हमारे पास आकार n का एक वर्गीकरण नेटवर्क है, हम आकार का एक नेटवर्क बना सकते हैं {{nowrap|''n'' + 1}} पहले से वर्गीकरण किए गए सबनेट में एक अतिरिक्त संख्या डालकर (प्रविष्टि वर्गीकरण के पीछे के सिद्धांत का उपयोग करके)। हम पहले इनपुट से सबसे कम मूल्य का चयन करके और फिर शेष मूल्यों को पुनरावर्ती रूप से वर्गीकरण करके (बबल वर्गीकरण के सिद्धांत का उपयोग करके) एक ही चीज़ को पूरा कर सकते हैं।).[[File:Recursive-bubble-sorting-network.svg|200px|thumb|एक वर्गीकरण  नेटवर्क पुनरावर्ती रूप से निर्मित होता है जो पहले सबसे बड़े मान को नीचे तक ले जाता है और फिर शेष तारों को छाँटता है। [[ बुलबुले की तरह ]] के आधार पर]]
+हम निवेशन और चयन के सिद्धांतों का उपयोग करके आसानी से किसी भी आकार के नेटवर्क का पुनरावर्ती रूप से निर्माण कर सकते हैं। यह मानते हुए कि हमारे पास आकार n का एक लघुपरिपथ नेटवर्क है, हम {{nowrap|''n'' + 1}} आकार का एक नेटवर्क बना सकते हैं, पहले से लघुपरिपथ किए गए सबनेट में एक अतिरिक्त संख्या डालकर (प्रविष्टि लघुपरिपथ के पीछे के सिद्धांत का उपयोग करके)। हम पहले इनपुट से सबसे कम आंकिक मान का चयन करके और फिर शेष आंकिक मानों को पुनरावर्ती रूप से लघुपरिपथ करके (बबल लघुपरिपथ के सिद्धांत का उपयोग करके) एक ही चीज़ को पूरा कर सकते हैं।).[[File:Recursive-bubble-sorting-network.svg|200px|thumb|एक लघुपरिपथ नेटवर्क पुनरावर्ती रूप से निर्मित होता है जो पहले सबसे बड़े मान को नीचे तक ले जाता है और फिर शेष तारों को [[बबल सोर्ट|बबल]] के आधार पर सॉर्ट करता है।]]
 {|
 | style="vertical-align: top;" |
-| style="vertical-align: top;" |[[File:Recursive-insertion-sorting-network.svg|200px|thumb|A sorting network constructed recursively that first sorts the first n wires, and then inserts the remaining value. Based on [[insertion sort]]]]
+| style="vertical-align: top;" |[[File:Recursive-insertion-sorting-network.svg|200px|thumb|एक [[लघुपरिपथ नेटवर्क]] पुनरावर्ती रूप से निर्मित होता है जो पहले n तारों को सॉर्ट करता है, और फिर शेष मान [[निवेशन]] क्रम के आधार पर सम्मिलित करता है। ]]
-|}इन दो वर्गीकरण  नेटवर्कों की संरचना बहुत समान है। दो अलग-अलग रूपांतर का निर्माण, जो एक साथ किए जा सकने वाले तुलनित्रों को एक साथ टूटकर गिर जाते हैं, यह दर्शाता है कि वास्तव में, वे समान हैं।<ref name="knuth"/>
+|}इन दो लघुपरिपथ नेटवर्कों की संरचना बहुत समान है। दो अलग-अलग रूपांतर का निर्माण, जो एक साथ किए जा सकने वाले लघुपरिपथ को एक साथ निष्क्रिय कर सकता है, यह दर्शाता है कि वास्तव में, वे समान हैं।<ref name="knuth"/>
 {|
-|style="vertical-align: top;"| [[File:Six-wire-bubble-sorting-network.svg|200px|thumb|Bubble sorting network]]
+|style="vertical-align: top;"| [[File:Six-wire-bubble-sorting-network.svg|200px|thumb|बबल सॉर्टिंग नेटवर्क]]
-|style="vertical-align: top;"| [[File:Six-wire-insertion-sorting-network.svg|200px|thumb|Insertion sorting network]]
+|style="vertical-align: top;"| [[File:Six-wire-insertion-sorting-network.svg|200px|thumb|निवेशन सॉर्टिंग नेटवर्क]]
-|style="vertical-align: top;"| [[File:Six-wire-pyramid-sorting-network.svg|200px|thumb|When allowing for parallel comparators, bubble sort and insertion sort are identical]]
+|style="vertical-align: top;"| [[File:Six-wire-pyramid-sorting-network.svg|200px|thumb|समांतर तुलनित्रों की अनुमति देते समय, बबल सॉर्ट और सम्मिलन सॉर्ट समान होते हैं]]
 |}
-सम्मिलन नेटवर्क (या समतुल्य, बबल नेटवर्क) की गहराई 2n - 3 है, [1] जहां n मानों की संख्या है। यह [[रैंडम-एक्सेस मशीनों]] द्वारा आवश्यक O(n log n) समय से बेहतर है, लेकिन यह पता चला है कि केवल O(log2 n) की गहराई वाले अधिक कुशल वर्गीकरण नेटवर्क हैं, जैसा कि नीचे वर्णित है।
+निवेशन नेटवर्क (या समतुल्य, बबल नेटवर्क) की गहनता 2n - 3 है, [1] जहां n मानों की संख्या है। यह [[रैंडम-एक्सेस मशीनों]] द्वारा आवश्यक O(n log n) समय से बेहतर है, लेकिन यह पता चला है कि केवल O(log2 n) की गहनता वाले अधिक कुशल लघुपरिपथ नेटवर्क हैं, जैसा कि नीचे वर्णित है।
 === शून्य-एक सिद्धांत ===
-हालांकि कुछ वर्गीकरण नेटवर्क (जैसे इंसर्शन/बबल सॉर्टर) की वैधता को साबित करना आसान है, लेकिन यह हमेशा इतना आसान नहीं होता है। वहाँ हैं {{math|''n''!}} में संख्याओं का क्रमपरिवर्तन {{mvar|n}}-वायर नेटवर्क, और उन सभी का परीक्षण करने में काफी समय लगेगा, खासकर जब {{mvar|n}} बड़ी है। परीक्षण मामलों की संख्या को काफी कम किया जा सकता है {{math|2<sup>''n''</sup>}}, तथाकथित शून्य-एक सिद्धांत का उपयोग करते हुए। जबकि अभी भी घातीय है, यह इससे छोटा है {{math|''n''!}} सभी के लिए {{math|''n'' ≥ 4}}, और अंतर बढ़ने के साथ काफी तेजी से बढ़ता है {{mvar|n}}.
+हालांकि कुछ लघुपरिपथ नेटवर्क (जैसे इंसर्शन/बबल सॉर्टर) की वैधता को प्रमाणित करना आसान है, लेकिन यह सदैव इतना आसान नहीं होता है। {{math|''n''!}} में संख्याओं का क्रमपरिवर्तन {{mvar|n}}-वायर नेटवर्क, और उन सभी का परीक्षण करने में अत्यधिक समय लगेगा, विशेषकर जब {{mvar|n}} दीर्घ हो। बड़ी मात्रा में इनपुट को लघुपरिपथ करने के लिए, नए लघुपरिपथ नेटवर्क का निर्माण किया जाना चाहिए। परीक्षण प्रकरणों की संख्या {{math|2<sup>''n''</sup>}} को तथाकथित शून्य-एक सिद्धांत का उपयोग करते हुए अत्यधिक कम किया जा सकता है। जबकि अभी भी यह इससे छोटा घातीय है, {{math|''n''!}} सभी के लिए {{math|''n'' ≥ 4}}, और {{mvar|n}} अंतर बढ़ने के साथ अत्यधिक तेजी से बढ़ता है।
-शून्य-एक सिद्धांत बताता है कि, यदि एक वर्गीकरण नेटवर्क सभी को सही ढंग से वर्गीकरण कर सकता है {{math|2<sup>''n''</sup>}} शून्य और एक का अनुक्रम, तो यह मनमाने ढंग से आदेशित इनपुट के लिए भी मान्य है। यह न केवल नेटवर्क की वैधता का पता लगाने के लिए आवश्यक परीक्षणों की संख्या में भारी कटौती करता है, बल्कि वर्गीकरण नेटवर्क के कई निर्माणों को बनाने में भी इसका बहुत उपयोग होता है।
+शून्य-एक सिद्धांत निर्दिष्ट करता है कि, यदि एक लघुपरिपथ नेटवर्क सभी को सही ढंग से लघुपरिपथ कर सकता है, शून्य और एक {{math|2<sup>''n''</sup>}} का अनुक्रम, तो यह अनियंत्रित पद्धति से आदेशित इनपुट के लिए भी मान्य है। यह न केवल नेटवर्क की वैधता का पता लगाने के लिए आवश्यक परीक्षणों की संख्या में भारी कटौती करता है, बल्कि लघुपरिपथ नेटवर्क के कई निर्माणों को बनाने में भी इसका बहुत उपयोग होता है।
-सिद्धांत को पहले तुलनित्रों के बारे में निम्नलिखित तथ्य को देखकर सिद्ध किया जा सकता है: जब एक [[मोनोटोनिक फ़ंक्शन]] कार्य करता है {{mvar|f}} इनपुट पर लागू होता है, अर्थात, {{mvar|x}} और {{mvar|y}} द्वारा प्रतिस्थापित किया जाता है {{math|''f''(''x'')}} और {{math|''f''(''y'')}}, तो तुलनाकारी पैदा करता है {{math|min(''f''(''x''), ''f''(''y'')) {{=}} ''f''(min(''x'', ''y''))}} और {{math|max(''f''(''x''), ''f''(''y'')) {{=}} ''f''(max(''x'', ''y''))}}. नेटवर्क की गहराई पर [[गणितीय प्रेरण]] द्वारा, इस परिणाम को [[लेम्मा (गणित)]] तक बढ़ाया जा सकता है, जिसमें कहा गया है कि यदि नेटवर्क अनुक्रम को बदल देता है {{math|''a''<sub>1</sub>, ..., ''a''<sub>''n''</sub>}} में {{math|''b''<sub>1</sub>, ..., ''b''<sub>''n''</sub>}}, यह बदल जाएगा {{math|''f''(''a''<sub>1</sub>), ..., ''f''(''a''<sub>''n''</sub>)}} में {{math|''f''(''b''<sub>1</sub>), ..., ''f''(''b''<sub>''n''</sub>)}}. मान लीजिए कि कुछ इनपुट {{math|''a''<sub>1</sub>, ..., ''a''<sub>''n''</sub>}} में दो वस्तु हैं {{math|''a<sub>i</sub>'' < ''a<sub>j</sub>''}}, और नेटवर्क गलत तरीके से आउटपुट में इनकी अदला-बदली करता है। फिर यह गलत तरीके से वर्गीकरण भी करेगा {{math|''f''(''a''<sub>1</sub>), ..., ''f''(''a''<sub>''n''</sub>)}} समारोह के लिए
+सिद्धांत को पहले लघुपरिपथ के बारे में निम्नलिखित तथ्य को देखकर सिद्ध किया जा सकता है: जब एक [[मोनोटोनिक फ़ंक्शन|मोनोटोनिक फलन]] {{mvar|f}} कार्य करता है तो वह इनपुट पर लागू होता है, अर्थात, {{mvar|x}} और {{mvar|y}} द्वारा प्रतिस्थापित किया जाता है {{math|''f''(''x'')}} और {{math|''f''(''y'')}}, तो लघुपरिपथ उत्पन्न करता है, {{math|min(''f''(''x''), ''f''(''y'')) {{=}} ''f''(min(''x'', ''y''))}} और {{math|max(''f''(''x''), ''f''(''y'')) {{=}} ''f''(max(''x'', ''y''))}}. नेटवर्क की गहनता पर [[गणितीय प्रेरण]] द्वारा, इस परिणाम को [[लेम्मा (गणित)]] तक बढ़ाया जा सकता है, जिसमें कहा गया है कि यदि नेटवर्क अनुक्रम को बदल देता है, {{math|''a''<sub>1</sub>, ..., ''a''<sub>''n''</sub>}} में {{math|''b''<sub>1</sub>, ..., ''b''<sub>''n''</sub>}}, यह बदल जाएगा, मान लीजिए कि {{math|''f''(''a''<sub>1</sub>), ..., ''f''(''a''<sub>''n''</sub>)}} में {{math|''f''(''b''<sub>1</sub>), ..., ''f''(''b''<sub>''n''</sub>)}}  कुछ इनपुट {{math|''a''<sub>1</sub>, ..., ''a''<sub>''n''</sub>}} में दो {{math|''a<sub>i</sub>'' < ''a<sub>j</sub>''}} वस्तु हैं, और नेटवर्क असामान्य तरीके से आउटपुट में इनकी अदला-बदली करता है। फिर यह असामान्य तरीके से लघुपरिपथ भी {{math|''f''(''a''<sub>1</sub>), ..., ''f''(''a''<sub>''n''</sub>)}} फलन के लिए करेगा।
 :<math>
@@ Line 46: / Line 46: @@
         \end{cases}
 </math>
-यह फ़ंक्शन मोनोटोनिक है, इसलिए हमारे पास [[कोंटरापज़िशन]] के रूप में शून्य-एक सिद्धांत है।<ref name="clrs"/>{{rp|640–641}}
+यह फलन मोनोटोनिक है, इसलिए हमारे पास [[कोंटरापज़िशन|प्रतिपरिवर्तित]] के रूप में शून्य-एक सिद्धांत है।<ref name="clrs"/>{{rp|640–641}}
-== वर्गीकरण नेटवर्क का निर्माण ==
+== लघुपरिपथ नेटवर्क का निर्माण ==
-गहराई के वर्गीकरण  नेटवर्क के निर्माण के लिए विभिन्न एल्गोरिदम मौजूद हैं {{math|''O''(log<sup>2</sup> ''n'')}} (इसलिए आकार {{math|''O''(''n'' log<sup>2</sup> ''n'')}}) जैसे बैचर ऑड-ईवन मर्जसॉर्ट, [[ बिटोनिक प्रकार |बिटोनिक प्रकार]], [[ शैल छँटाई ]] और [[ जोड़ीदार छँटाई नेटवर्क |जोड़ीदार वर्गीकरण  नेटवर्क]]। ये नेटवर्क अक्सर व्यवहार में उपयोग किए जाते हैं।
+गहनता के लघुपरिपथ नेटवर्क के निर्माण के लिए विभिन्न कलन विधि {{math|''O''(log<sup>2</sup> ''n'')}} उपस्थित हैं (इसलिए आकार {{math|''O''(''n'' log<sup>2</sup> ''n'')}}) जैसे बैचर ऑड-ईवन मर्जसॉर्ट, [[ बिटोनिक प्रकार |बिटोनिक प्रकार]], [[ शैल छँटाई |शैल लघुपरिपथ]] और [[ जोड़ीदार छँटाई नेटवर्क |संयुग्मित लघुपरिपथ नेटवर्क]]। ये नेटवर्क प्रायः व्यवहार में उपयोग किए जाते हैं। बड़ी मात्रा में इनपुट को लघुपरिपथ करने के लिए, नए लघुपरिपथ नेटवर्क का निर्माण किया जाना चाहिए।
-गहराई के नेटवर्क का निर्माण करना भी संभव है {{math|''O''(log ''n'')}} (इसलिए आकार {{math|''O''(''n'' log ''n'')}}) एकेएस नेटवर्क नामक एक निर्माण का उपयोग करते हुए, इसके खोजकर्ता मिक्लोस अजताई, जानोस कोमलोस (गणितज्ञ)|कोमलोस, और एंड्रे स्ज़ेमेरीडी|ज़ेमेरीडी के नाम पर।<ref>{{Cite conference | doi = 10.1145/800061.808726| title = An {{math|O(n log n)}} sorting network| work = Proceedings of the fifteenth annual ACM symposium on Theory of computing | conference = [[Symposium on Theory of Computing|STOC]] '83| pages = 1–9| year = 1983| last1 = Ajtai | first1 = M. |author-link1 = Miklós Ajtai| last2 = Komlós | first2 = J. |author-link2 = János Komlós (mathematician)| last3 = Szemerédi | first3 = E. |author-link3 = Endre Szemerédi| isbn = 0-89791-099-0}}</ref> जबकि एक महत्वपूर्ण सैद्धांतिक खोज, [[बिग-ओ नोटेशन]] द्वारा छिपे हुए बड़े रैखिक स्थिरांक के कारण एकेएस नेटवर्क के पास बहुत सीमित व्यावहारिक अनुप्रयोग है।<ref name="clrs"/>{{rp|653}} ये आंशिक रूप से [[विस्तारक ग्राफ]] के निर्माण के कारण हैं।
+गहनता के नेटवर्क {{math|''O''(log ''n'')}} का निर्माण करना भी संभव है (इसलिए आकार {{math|''O''(''n'' log ''n'')}}), एकेएस नेटवर्क नामक एक निर्माण का उपयोग करते हुए, इसके खोजकर्ता मिक्लोस अजताई, जानोस कोमलोस (गणितज्ञ) कोमलोस, और एंड्रे स्ज़ेमेरीडी के नाम पर हुई,<ref>{{Cite conference | doi = 10.1145/800061.808726| title = An {{math|O(n log n)}} sorting network| work = Proceedings of the fifteenth annual ACM symposium on Theory of computing | conference = [[Symposium on Theory of Computing|STOC]] '83| pages = 1–9| year = 1983| last1 = Ajtai | first1 = M. |author-link1 = Miklós Ajtai| last2 = Komlós | first2 = J. |author-link2 = János Komlós (mathematician)| last3 = Szemerédi | first3 = E. |author-link3 = Endre Szemerédi| isbn = 0-89791-099-0}}</ref> जबकि एक महत्वपूर्ण सैद्धांतिक खोज, [[बिग-ओ नोटेशन]] द्वारा छिपे हुए बड़े रैखिक स्थिरांक के कारण एकेएस नेटवर्क के पास बहुत सीमित व्यावहारिक अनुप्रयोग दर्शाता है।<ref name="clrs"/>{{rp|653}} ये आंशिक रूप से [[विस्तारक ग्राफ]] के निर्माण के कारण हैं।
-एकेएस नेटवर्क का एक सरलीकृत संस्करण 1990 में माइकल एस. पैटर्सन द्वारा वर्णित किया गया था, जिन्होंने नोट किया था कि डेप्थ बाउंड के लिए प्राप्त स्थिरांक अभी भी व्यावहारिक मूल्य के निर्माण को रोकते हैं।<ref>{{Cite journal | doi = 10.1007/BF01840378| title = Improved sorting networks with {{math|''O''(log ''N'')}} depth| journal = Algorithmica| volume = 5| issue = 1–4| pages = 75–92| year = 1990| last1 = Paterson | first1 = M. S.| s2cid = 2064561}}</ref>
+एकेएस नेटवर्क का एक सरलीकृत संस्करण 1990 में माइकल एस. पैटर्सन द्वारा वर्णित किया गया था, जिन्होंने नोट किया था कि डेप्थ बाउंड के लिए प्राप्त स्थिरांक अभी भी व्यावहारिक आंकिक मान के निर्माण को रोकते हैं।<ref>{{Cite journal | doi = 10.1007/BF01840378| title = Improved sorting networks with {{math|''O''(log ''N'')}} depth| journal = Algorithmica| volume = 5| issue = 1–4| pages = 75–92| year = 1990| last1 = Paterson | first1 = M. S.| s2cid = 2064561}}</ref>
-एक और हालिया निर्माण को आकार का ज़िग-ज़ैग वर्गीकरण नेटवर्क कहा जाता है {{math|''O''(''n'' log ''n'')}} की खोज माइकल टी. गुडरिच ने 2014 में की थी।<ref>{{cite book|last1=Goodrich|first1=Michael|authorlink1=Michael T. Goodrich|arxiv=1403.2777|title=Zig-zag Sort: A Simple Deterministic Data-Oblivious Sorting Algorithm Running in O(n log n) Time|date=March 2014|doi=10.1145/2591796.2591830|journal=Proceedings of the 46th Annual ACM Symposium on Theory of Computing - STOC '14|pages=684–693|isbn=9781450327107|s2cid=947950}}</ref> जबकि इसका आकार एकेएस नेटवर्क की तुलना में बहुत छोटा है, इसकी गहराई {{math|''O''(''n'' log ''n'')}} इसे समानांतर कार्यान्वयन के लिए अनुपयुक्त बनाता है।
+एक और हालिया निर्माण को आकार का ज़िग-ज़ैग लघुपरिपथ नेटवर्क कहा जाता है, {{math|''O''(''n'' log ''n'')}} की खोज माइकल टी. गुडरिच ने 2014 में की थी।<ref>{{cite book|last1=Goodrich|first1=Michael|authorlink1=Michael T. Goodrich|arxiv=1403.2777|title=Zig-zag Sort: A Simple Deterministic Data-Oblivious Sorting Algorithm Running in O(n log n) Time|date=March 2014|doi=10.1145/2591796.2591830|journal=Proceedings of the 46th Annual ACM Symposium on Theory of Computing - STOC '14|pages=684–693|isbn=9781450327107|s2cid=947950}}</ref> जबकि इसका आकार एकेएस नेटवर्क की लघुपरिपथ में बहुत छोटा है, इसकी गहनता {{math|''O''(''n'' log ''n'')}} इसे समानांतर कार्यान्वयन के लिए अनुपयुक्त बनाता है।
-=== इष्टतम वर्गीकरण नेटवर्क ===
+=== इष्टतम लघुपरिपथ नेटवर्क ===
-इनपुट की छोटी, निश्चित संख्या के लिए {{mvar|n}}, न्यूनतम गहराई (अधिकतम समांतर निष्पादन के लिए) या न्यूनतम आकार (तुलनित्रों की संख्या) के साथ इष्टतम वर्गीकरण नेटवर्क का निर्माण किया जा सकता है। इन नेटवर्कों का उपयोग बड़े वर्गीकरण नेटवर्कों के प्रदर्शन को बढ़ाने के लिए किया जा सकता है, जो [[फूट डालो और जीतो एल्गोरिथम]] के निर्माण से उत्पन्न होता है, उदाहरण के लिए, बैचर, रिकर्सन को जल्दी रोककर और बेस केस के रूप में इष्टतम नेट सम्मिलित करके।<ref name="parberry91">{{cite journal |first=Ian |last=Parberry |title=नाइन-इनपुट सॉर्टिंग नेटवर्क के लिए कंप्यूटर असिस्टेड ऑप्टिमल डेप्थ लोअर बाउंड|journal=Mathematical Systems Theory |volume=24 |pages=101–116 |year=1991 |url=http://larc.unt.edu/ian/pubs/9-input.pdf |doi=10.1007/bf02090393|citeseerx=10.1.1.712.219 |s2cid=7077160 }}</ref> निम्न तालिका उन छोटे नेटवर्कों के लिए इष्टतमता परिणामों का सार प्रस्तुत करती है जिनके लिए इष्टतम गहराई ज्ञात है:
+इनपुट की छोटी, निश्चित संख्या के लिए {{mvar|n}}, न्यूनतम गहनता (अधिकतम समांतर निष्पादन के लिए) या न्यूनतम आकार (लघुपरिपथ की संख्या) के साथ इष्टतम लघुपरिपथ नेटवर्क का निर्माण किया जा सकता है। इन नेटवर्कों का उपयोग बड़े लघुपरिपथ नेटवर्कों के प्रदर्शन को बढ़ाने के लिए किया जा सकता है, जो [[फूट डालो और जीतो एल्गोरिथम|कलन विधि]] के निर्माण से उत्पन्न होता है, उदाहरण के लिए, बैचर, रिकर्सन को जल्दी रोककर और बेस केस के रूप में इष्टतम नेट सम्मिलित करके<ref name="parberry91">{{cite journal |first=Ian |last=Parberry |title=नाइन-इनपुट सॉर्टिंग नेटवर्क के लिए कंप्यूटर असिस्टेड ऑप्टिमल डेप्थ लोअर बाउंड|journal=Mathematical Systems Theory |volume=24 |pages=101–116 |year=1991 |url=http://larc.unt.edu/ian/pubs/9-input.pdf |doi=10.1007/bf02090393|citeseerx=10.1.1.712.219 |s2cid=7077160 }}</ref> निम्न तालिका उन छोटे नेटवर्कों के लिए इष्टतमता परिणामों का सार प्रस्तुत करती है जिनके लिए इष्टतम गहनता ज्ञात है:
 {| class="wikitable" style="text-align: center;"
@@ Line 66: / Line 66: @@
 |17
 |-
-! style="text-align: left;" | Depth<ref name="codish_end_game">{{cite conference |last1=Codish |first1=Michael |last2=Cruz-Filipe |first2=Luís |last3=Ehlers |first3=Thorsten |last4=Müller |first4=Mike |last5= Schneider-Kamp |first5=Peter |title=Sorting Networks: to the End and Back Again |arxiv=1507.01428 |year=2015|bibcode=2015arXiv150701428C }}</ref>
+! style="text-align: left;" | गहनता<ref name="codish_end_game">{{cite conference |last1=Codish |first1=Michael |last2=Cruz-Filipe |first2=Luís |last3=Ehlers |first3=Thorsten |last4=Müller |first4=Mike |last5= Schneider-Kamp |first5=Peter |title=Sorting Networks: to the End and Back Again |arxiv=1507.01428 |year=2015|bibcode=2015arXiv150701428C }}</ref>
 | 0 || 1 || 3 || 3 || 5 || 5 || 6 || 6 || 7 || 7 || 8 || 8 || 9 || 9 || 9 || 9
 |10
 |-
-! style="text-align: left;" | Size, upper bound<ref name="codish"/>
+! style="text-align: left;" | आकार, ऊपरी सीमा<ref name="codish"/>
 | 0 || 1 || 3 || 5 || 9 || 12 || 16 || 19 || 25 || 29 || 35 || 39 || 45 || 51 || 56 || 60
 |71
 |-
-! style="text-align: left;" | Size, lower bound (if different)<ref name="vvoorhis">Obtained by Van Voorhis lemma and the value {{math|''S''(11) {{=}} 35}}</ref>
+! style="text-align: left;" | आकार, निचली सीमा (यदि भिन्न हो)<ref name="vvoorhis">Obtained by Van Voorhis lemma and the value {{math|''S''(11) {{=}} 35}}</ref>
 |  ||  ||  ||  ||  ||  ||  ||  ||  ||  ||  ||  || 43 || 47 || 51 || 55
 |60
 |}
-बड़े नेटवर्क के लिए वर्तमान में न तो इष्टतम गहराई और न ही इष्टतम आकार ज्ञात है। अब तक ज्ञात सीमाएँ नीचे दी गई तालिका में दी गई हैं:
+बड़े नेटवर्क के लिए वर्तमान में न तो इष्टतम गहनता और न ही इष्टतम आकार ज्ञात है। अब तक ज्ञात सीमाएँ नीचे दी गई तालिका में दी गई हैं:
 {| class="wikitable" style="text-align: center;"
@@ Line 85: / Line 85: @@
 | style="width: 30px;" | 18 || style="width: 30px;" | 19 || style="width: 30px;" | 20 || style="width: 30px;" | 21 || style="width: 30px;" | 22 || style="width: 30px;" | 23 || style="width: 30px;" | 24 || style="width: 30px;" | 25 || style="width: 30px;" | 26 || style="width: 30px;" | 27 || style="width: 30px;" | 28 || style="width: 30px;" | 29 || style="width: 30px;" | 30 || style="width: 30px;" | 31 || style="width: 30px;" | 32
 |-
-! style="text-align: left;" | Depth, upper bound<ref name="codish_end_game"/><ref>{{cite journal |last1=Ehlers |first1=Thorsten |title=Merging almost sorted sequences yields a 24-sorter |journal=Information Processing Letters |date=February 2017 |volume=118 |pages=17–20 |doi=10.1016/j.ipl.2016.08.005}}</ref><ref name="sorterhunter">{{cite web |last1=Dobbelaere |first1=Bert |title=SorterHunter |url=https://github.com/bertdobbelaere/SorterHunter |website=GitHub |access-date=2 Jan 2022}}</ref>
+! style="text-align: left;" | गहनता, ऊपरी सीमा<ref name="codish_end_game"/><ref>{{cite journal |last1=Ehlers |first1=Thorsten |title=Merging almost sorted sequences yields a 24-sorter |journal=Information Processing Letters |date=February 2017 |volume=118 |pages=17–20 |doi=10.1016/j.ipl.2016.08.005}}</ref><ref name="sorterhunter">{{cite web |last1=Dobbelaere |first1=Bert |title=SorterHunter |url=https://github.com/bertdobbelaere/SorterHunter |website=GitHub |access-date=2 Jan 2022}}</ref>
 | 11 || 11 || 11 || 12 || 12 || 12 || 12 || 13 || 13 || 14 || 14 || 14 || 14 || 14
 |14
 |-
-! style="text-align: left;" | Depth, lower bound<ref name="codish_end_game"/>
+! style="text-align: left;" | गहनता, निचली सीमा<ref name="codish_end_game"/>
 | 10 || 10 || 10 || 10 || 10 || 10 || 10 || 10 || 10 || 10 || 10 || 10 || 10 || 10
 |10
 |-
-! style="text-align: left;" | Size, upper bound<ref name="sorterhunter"/>
+! style="text-align: left;" | आकार, ऊपरी सीमा<ref name="sorterhunter"/>
 | 77 || 85 || 91 || 99 || 107 || 114 || 120 || 131 || 139 || 148 || 155 || 165 || 172 || 180
 |185
 |-
-! style="text-align: left;" | Size, lower bound<ref name="vvoorhis"/>
+! style="text-align: left;" | आकार, निचली सीमा<ref name="vvoorhis"/>
 | 65 || 70 || 75 || 80 || 85 || 90 || 95 || 100 || 105 || 110 || 115 || 120 || 125 || 130
 |135
 |}
-पहले सोलह गहराई-इष्टतम नेटवर्क नुथ की [[कंप्यूटर प्रोग्रामिंग की कला]] में सूचीबद्ध हैं,<ref name="knuth">{{cite book |first=D. E. |last=Knuth |author-link=Donald Knuth |title=The Art of Computer Programming, Volume 3: Sorting and Searching |edition=Second |publisher=Addison–Wesley |year=1997 |isbn=978-0-201-89685-5 |pages=219–247|title-link=The Art of Computer Programming }} Section 5.3.4: Networks for Sorting.</ref> और 1973 संस्करण के बाद से हैं; हालाँकि, जबकि पहले आठ की इष्टतमता रॉबर्ट डब्ल्यू फ्लॉयड और नुथ द्वारा 1960 के दशक में स्थापित की गई थी, यह संपत्ति 2014 तक अंतिम छह के लिए सिद्ध नहीं हुई थी<ref name="bundala_zavodny">{{Cite book| doi = 10.1007/978-3-319-04921-2_19| title = इष्टतम सॉर्टिंग नेटवर्क| journal = Language and Automata Theory and Applications| volume = 8370| pages = 236–247| series = Lecture Notes in Computer Science| year = 2014| last1 = Bundala | first1 = D. | last2 = Závodný | first2 = J. | isbn = 978-3-319-04920-5| arxiv = 1310.6271| s2cid = 16860013}}</ref> (मामले नौ और दस का 1991 में फैसला किया जा चुका है<ref name="parberry91"/>).
+पहले सोलह गहनता-इष्टतम नेटवर्क नुथ की [[कंप्यूटर प्रोग्रामिंग की कला]] में सूचीबद्ध हैं,<ref name="knuth">{{cite book |first=D. E. |last=Knuth |author-link=Donald Knuth |title=The Art of Computer Programming, Volume 3: Sorting and Searching |edition=Second |publisher=Addison–Wesley |year=1997 |isbn=978-0-201-89685-5 |pages=219–247|title-link=The Art of Computer Programming }} Section 5.3.4: Networks for Sorting.</ref> और 1973 संस्करण के बाद से हैं; हालाँकि, जबकि पहले आठ की इष्टतमता रॉबर्ट डब्ल्यू फ्लॉयड और नुथ द्वारा 1960 के दशक में स्थापित की गई थी, यह विशेषता 2014 तक अंतिम छह के लिए सिद्ध नहीं हुई थी<ref name="bundala_zavodny">{{Cite book| doi = 10.1007/978-3-319-04921-2_19| title = इष्टतम सॉर्टिंग नेटवर्क| journal = Language and Automata Theory and Applications| volume = 8370| pages = 236–247| series = Lecture Notes in Computer Science| year = 2014| last1 = Bundala | first1 = D. | last2 = Závodný | first2 = J. | isbn = 978-3-319-04920-5| arxiv = 1310.6271| s2cid = 16860013}}</ref> (प्रकरण नौ और दस का 1991 में फैसला किया जा चुका है<ref name="parberry91"/>).
-एक से बारह इनपुट के लिए, न्यूनतम (यानी आकार-इष्टतम) वर्गीकरण  नेटवर्क ज्ञात हैं, और उच्च मूल्यों के लिए, उनके आकार पर कम सीमाएँ {{math|''S''(''n'')}} वैन वूरिस के कारण लेम्मा का उपयोग करके आगमनात्मक रूप से प्राप्त किया जा सकता है<ref name="knuth"/>(पृष्ठ 240): {{math|''S''(''n'') ≥ ''S''(''n'' − 1) + ⌈log<sub>2</sub>''n''⌉}}. पहले दस इष्टतम नेटवर्क 1969 के बाद से जाने जाते हैं, पहले आठ को फ़्लॉइड और नुथ के काम के बाद से फिर से इष्टतम के रूप में जाना जाता है, लेकिन मामलों की इष्टतमता {{math|''n'' {{=}} 9}} और {{math|''n'' {{=}} 10}} को हल करने में 2014 तक का समय लगा।<ref name="codish">{{cite conference |last1=Codish |first1=Michael |last2=Cruz-Filipe |first2=Luís |last3=Frank |first3=Michael |last4= Schneider-Kamp |first4=Peter |title=नौ इनपुट (और दस के लिए उनतीस) को छाँटते समय पच्चीस तुलनित्र इष्टतम होते हैं|conference=Proc. Int'l Conf. Tools with AI (ICTAI) |arxiv=1405.5754 |year=2014 |pages=186–193|bibcode=2014arXiv1405.5754C }}</ref>
+एक से बारह इनपुट के लिए, न्यूनतम (अर्थात आकार-इष्टतम) लघुपरिपथ नेटवर्क ज्ञात हैं, और उच्च आंकिक मानों के लिए, उनके आकार पर कम सीमाएँ {{math|''S''(''n'')}} वैन वूरिस के कारण लेम्मा का उपयोग करके आगमनात्मक रूप से प्राप्त किया जा सकता है<ref name="knuth"/>(पृष्ठ 240): {{math|''S''(''n'') ≥ ''S''(''n'' − 1) + ⌈log<sub>2</sub>''n''⌉}} पहले दस इष्टतम नेटवर्क 1969 के बाद से जाने जाते हैं, पहले आठ को फ़्लॉइड और नुथ के काम के बाद से फिर से इष्टतम के रूप में जाना जाता है, लेकिन प्रकरणों की इष्टतमता {{math|''n'' {{=}} 9}} और {{math|''n'' {{=}} 10}} को हल करने में 2014 तक का समय लगा।<ref name="codish">{{cite conference |last1=Codish |first1=Michael |last2=Cruz-Filipe |first2=Luís |last3=Frank |first3=Michael |last4= Schneider-Kamp |first4=Peter |title=नौ इनपुट (और दस के लिए उनतीस) को छाँटते समय पच्चीस तुलनित्र इष्टतम होते हैं|conference=Proc. Int'l Conf. Tools with AI (ICTAI) |arxiv=1405.5754 |year=2014 |pages=186–193|bibcode=2014arXiv1405.5754C }}</ref> जिसके लिए सबसे छोटे ज्ञात लघुपरिपथ नेटवर्क की इष्टतमता {{math|''n'' {{=}} 11}} और {{math|''n'' {{=}} 12}} 2020 में हल किया गया था।<ref name="harder">{{cite arXiv |eprint=2012.04400 |last1=Harder |first1=Jannis |title=An Answer to the Bose-Nelson Sorting Problem for 11 and 12 Channels |year=2020 |class=cs.DS }}</ref><ref name="knuth"/>
-के लिए सबसे छोटे ज्ञात वर्गीकरण  नेटवर्क की इष्टतमता {{math|''n'' {{=}} 11}} और {{math|''n'' {{=}} 12}} 2020 में हल किया गया था।<ref name="harder">{{cite arXiv |eprint=2012.04400 |last1=Harder |first1=Jannis |title=An Answer to the Bose-Nelson Sorting Problem for 11 and 12 Channels |year=2020 |class=cs.DS }}</ref><ref name="knuth"/>
-[[ जेनेटिक एल्गोरिद्म ]] का उपयोग करके इष्टतम वर्गीकरण नेटवर्क को डिजाइन करने में कुछ काम किया गया है: डी. नुथ ने उल्लेख किया है कि सबसे छोटा ज्ञात वर्गीकरण नेटवर्क {{math|''n'' {{=}} 13}} 1995 में ह्यूग्स जुइल द्वारा आनुवंशिक प्रजनन की एक विकासवादी प्रक्रिया का अनुकरण करके पाया गया था<ref name="knuth"/>(पृ. 226), और उसके लिए न्यूनतम गहराई वर्गीकरण नेटवर्क {{math|''n'' {{=}} 9}} और {{math|''n'' {{=}} 11}} 2001 में लोरेन श्वीबर्ट द्वारा आनुवंशिक विधियों का उपयोग करते हुए पाए गए थे<ref name="knuth"/>(पृष्ठ 229)।
+[[ जेनेटिक एल्गोरिद्म |उत्पत्ति सम्बन्धी कलन विधि]] का उपयोग करके इष्टतम लघुपरिपथ नेटवर्क को डिजाइन करने में कुछ काम किया गया है: डी. नुथ ने उल्लेख किया है कि सबसे छोटा ज्ञात लघुपरिपथ नेटवर्क {{math|''n'' {{=}} 13}} 1995 में ह्यूग्स जुइल द्वारा उत्पत्ति सम्बन्धी कलन विधि एक विकासवादी प्रक्रिया का अनुकरण करके पाया गया था<ref name="knuth"/>(पृ. 226), और उसके लिए न्यूनतम गहनता लघुपरिपथ नेटवर्क {{math|''n'' {{=}} 9}} और {{math|''n'' {{=}} 11}} 2001 में लोरेन श्वीबर्ट द्वारा आनुवंशिक विधियों का उपयोग करते हुए पाए गए थे<ref name="knuth"/>(पृष्ठ 229)।
-=== वर्गीकरण  नेटवर्क के परीक्षण की जटिलता ===
+=== लघुपरिपथ नेटवर्क के परीक्षण की जटिलता ===
-जब तक पी बनाम एनपी | पी = एनपी, परीक्षण की समस्या यह नहीं है कि उम्मीदवार नेटवर्क एक वर्गीकरण नेटवर्क है, समस्या के [[सह-एनपी]]-पूर्ण होने के कारण बड़े आकार के नेटवर्क के लिए मुश्किल रहने की संभावना है।<ref name=parberry>{{cite conference |last=Parberry|first=Ian|title=इष्टतम सॉर्टिंग नेटवर्क सत्यापन की कम्प्यूटेशनल जटिलता पर|journal=Proc. PARLE '91: Parallel Architectures and Languages Europe, Volume I: Parallel Architectures and Algorithms, Eindhoven, the Netherlands |year=1991|pages=252–269}}</ref>
+जब तक P = NP, परीक्षण की समस्या यह नहीं है कि पदान्वेषी नेटवर्क एक लघुपरिपथ नेटवर्क है, समस्या यह है के [[सह-एनपी|co-NP]]-पूर्ण होने के कारण बड़े आकार के नेटवर्क के लिए निरंतर क्रियाशील बने रहने की संभावना मुश्किल है।<ref name=parberry>{{cite conference |last=Parberry|first=Ian|title=इष्टतम सॉर्टिंग नेटवर्क सत्यापन की कम्प्यूटेशनल जटिलता पर|journal=Proc. PARLE '91: Parallel Architectures and Languages Europe, Volume I: Parallel Architectures and Algorithms, Eindhoven, the Netherlands |year=1991|pages=252–269}}</ref>
@@ Line 128: / Line 127: @@
 *[http://optimizacion.cic.ipn.mx/sortingnetworks/ Sorting Networks validity]
-{{sorting}}
-[[Category: कंप्यूटर इंजीनियरिंग]] [[Category: छँटाई एल्गोरिदम]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 21/03/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:कंप्यूटर इंजीनियरिंग]]
+[[Category:छँटाई एल्गोरिदम]]

Anonymous

Search

लघुपरिपथ नेटवर्क: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 15:27, 19 April 2023

Contents