Comparison Networks Kya Hai

Comparison नेटवर्क एक प्रकार का सॉर्टिंग नेटवर्क है जो हमेशा अपने इनपुट को सॉर्ट करता है. तारों और तुलनित्र में Comparison नेटवर्क शामिल है. एक तुलनित्र एक उपकरण है जिसमें दो इनपुट (x, y) और आउटपुट (x ', y') हैं यह निम्नलिखित कार्य करता है.

x' = min(x, y),
y' = max(x, y) 

तुलनित्र पारंपरिक रूप से एकल ऊर्ध्वाधर रेखाओं के रूप में खींचे जाते हैं जहां इनपुट बाईं ओर होता है और दाएं तरफ आउटपुट. छोटे इनपुट मानों को शीर्ष आउटपुट पर रखा जाता है जबकि बड़े इनपुट मानों को नीचे आउटपुट पर रखा जाता है. इस प्रकार तुलनित्र को इसके दो इनपुटों को छांटने के रूप में माना जा सकता है. यह माना जाता है कि प्रत्येक तुलनित्र ओ (1) समय में संचालित होता है यानी इनपुट मानों की उपस्थिति और आउटपुट के उत्पादन के बीच का समय निरंतर होता है.

Comparison नेटवर्क का दूसरा घटक यानी तारों एक मान को एक स्थान से दूसरे स्थान तक पहुंचाने का कार्य करता है. ये या तो नेटवर्क इनपुट वायर या नेटवर्क आउटपुट वायर होते हैं. तार एक तुलनित्र के इनपुट को दूसरे के आउटपुट से जोड़ने में सक्षम हैं.

तुलनित्र द्वारा आउटपुट तभी उत्पन्न किया जाता है जब उसके इनपुट मान दोनों उपलब्ध हों. अब यह मानते हुए कि प्रत्येक तुलनित्र को इकाई समय लगता है रनिंग टाइम को परिभाषित किया जा सकता है. रनिंग टाइम आउटपुट तारों द्वारा मूल्यों को प्राप्त करने के लिए लिया जाता है इनपुट वायर के बाद उनके मान प्राप्त होते हैं। औपचारिक रूप से निम्नानुसार परिभाषित किया गया है. Comparison नेटवर्क के एक इनपुट वायर की गहराई 0. है यदि d1 और d2 दो इनपुट तारों की गहराई हैं तो आउटपुट तारों की गहराई अधिकतम (d1, d2) + 1. एक तुलनित्र की गहराई को गहराई के रूप में परिभाषित किया गया है इसके आउटपुट तार.

Properties

  1. ग्राफ को चक्रीय होना आवश्यक है

  2. सभी Comparison नेटवर्क सॉर्टिंग नेटवर्क नहीं हैं.

  3. इनपुट उपलब्ध होने पर ही आउटपुट का उत्पादन किया जाता है.

  4. यदि इनपुट उपलब्ध है तो कंपैरिटर समानांतर में प्रक्रिया करते हैं.

  5. सॉर्टिंग नेटवर्क एक Comparison नेटवर्क है जहां आउटपुट सॉर्ट किया जाता है.

  6. Comparison नेटवर्क एक प्रक्रिया की तरह है जो यह बताती है कि Comparison कैसे की जाती है