सॉर्टिंग और टोपोलॉजिकल-सॉर्टिंग के बीच क्या अंतर है?

Question

सॉर्टिंग और टोपोलॉजिकल-सॉर्टिंग के बीच क्या अंतर है?

क्या वे समान या अलग हैं?

Answer 1

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

कुल आदेश का अर्थ है कि, दोहराने की अनुपस्थिति में, जब आप कुछ सॉर्ट करते हैं, तो आपको एक अद्वितीय उचित उत्तर मिल जाएगा। यदि आप 3, 6, 2 आरोही क्रम में क्रमबद्ध करते हैं, तो आपको बेहतर एक जवाब मिल गया था: 2, 3, 6.

आंशिक क्रम थोड़ा कम है। कैननिकल उदाहरण वह क्रम है जिसमें आप अपने कपड़े डालते हैं: आप अपने शॉर्ट्स, फिर अपने पैंट, फिर अपने मोजे, फिर अपने जूते डाल सकते हैं। यह एक वैध आदेश है। या आप शॉर्ट्स, मोजे, पैंट, जूते कर सकते हैं। लेकिन सहजता से, आप शॉर्ट्स, पैंट, जूते, मोजे नहीं कर सकते हैं। जूते के बाद मोजे लगाने के लिए यह समझ में नहीं आता है।

उस ड्रेसिंग उदाहरण को औपचारिक बनाने के लिए, आप आम तौर पर नोड्स के रूप में क्रियाओं ("जूते पर डाल") के साथ एक निर्भरता ग्राफ दिखाते हैं, और निर्देश दिखाते हैं कि नोड को अन्य नोड्स से पहले क्या होना चाहिए। एक टोपोलॉजिकल सॉर्ट एक ग्राफ में सभी नोड्स का ऑर्डरिंग होता है जो कि arcs का सम्मान करता है। मतलब, अगर मोजे से जूते तक चाप है, तो ऑर्डर में जूते से पहले मोजे बेहतर होते हैं।

तो फिर, एक सार स्तर पर, वे जुड़े हुए हैं। लेकिन वे बिल्कुल वही बात नहीं हैं।

Answer 2

टॉपोलॉजिकल सॉर्ट आमतौर पर कुल आंशिक क्रम का अनुपालन करता है जो कुछ आंशिक क्रम का अनुपालन करता है, उदाहरण के लिए एक निर्देशित विश्वकोश ग्राफ में पहुंच क्षमता।

Answer 3

यदि कुल ऑर्डर उपलब्ध है तो प्रत्येक ऑब्जेक्ट की तुलना प्रत्येक ऑब्जेक्ट से की जा सकती है। इस मामले में आप wrt सॉर्ट कर सकते हैं। वह आदेश उदाहरण पूर्णांक wrt हैं। > (या <, या < =, ...) या स्ट्रिंग wrt। लेक्सिकोोग्राफिक ऑर्डरिंग। यदि आपके पास कुल ऑर्डर सॉर्टिंग संभव है।

यदि केवल आंशिक आदेश उपलब्ध है, तो प्रत्येक ऑब्जेक्ट की तुलना अन्य ऑब्जेक्ट से नहीं की जा सकती है। कुछ वस्तुओं के बीच केवल एक रिश्ता उपलब्ध है। एक उदाहरण संकलन इकाइयों के बीच निर्भरता है। टॉपोलॉजिकल सॉर्टिंग ऑब्जेक्ट्स को ऑर्डर करने का कार्य है जैसे कि आंशिक क्रम का सम्मान किया जाता है (उदाहरण के लिए इकाइयों को संकलित करके जो इन इकाइयों के बाद किसी अन्य इकाई पर निर्भर करते हैं)। यहां कई समाधान (यानी ऑर्डरिंग) संभव हैं: यदि ए बी पर निर्भर करता है और कुछ अन्य इकाई सी है, तो संभव संकलन अनुक्रम बी, ए, सी और सी, ए, बी (प्रत्येक अनुक्रम जहां ए बी से पहले संकलित किया गया है) हैं।

Answer 4

स्थलीय क्रम में, हम partially ordered set पर काम करते हैं लेकिन सामान्य सॉर्टिंग में, हम total ordered set पर काम करते हैं।

एक स्थलीय प्रकार में सेट के तत्वों की एक जोड़ी के बीच कोई संबंध नहीं है, जैसे निर्देशित ग्राफ में, कुछ नोड्स के बीच कोई संबंध नहीं है। सामान्य सॉर्टिंग में, सेट के तत्वों के सभी जोड़े का संबंध होता है। उदाहरण के लिए, संख्याओं के सेट में हमारे पास <,>, = सभी जोड़ों के बीच संबंध है, इसलिए यह कुल आदेश दिया गया है।