शायद एक छोटे से उदाहरण के साथ सबसे अच्छा सचित्र।
संबंधों को देखते हुएआंशिक रूप से आदेशित सूची को सॉर्ट करने का सबसे अच्छा तरीका क्या है?
A < B < C
A < P < Q
सही आउटपुट
ABCPQ or APQBC or APBCQ ... etc.
दूसरे शब्दों में हो सकता है, किसी भी आदेश है, जिसमें दिए गए रिश्तों पकड़ मान्य है।
मुझे उस समाधान में सबसे रूचि है जो कार्यान्वित करने के लिए सबसे आसान है, लेकिन गति और समय में सर्वश्रेष्ठ ओ (एन) भी दिलचस्प है।
इसे topological sorting कहा जाता है।
मानक एल्गोरिदम न्यूनतम तत्व को आउटपुट करना है, फिर इसे हटाएं और पूरा होने तक दोहराएं।
कई प्रकार के करो। पहले नियम के अनुसार पहले क्रमबद्ध करें, फिर दूसरे के अनुसार और इसी तरह के अनुसार। काम करना चाहिए, जब तक आपके नियमों में विरोधाभास न हो। लागू करने के लिए पर्याप्त आसान है।
यह सिर्फ एक उदाहरण है - सामान्य –
में केवल 2 नियम नहीं हैं, मुझे यकीन नहीं है कि नियमों की संख्या एक समस्या है। नतीजा अभी भी सही होगा। शायद थोड़ा प्रदर्शन मुद्दा। – user54579
और स्थिर स्थिर होना महत्वपूर्ण है –
आप बार-बार अनुक्रम के साथ C++ में make_heap, pop_heap को कॉल कर सकते हैं।
क्या आप दो क्रमबद्ध सूचियों को मर्ज करने का तरीका मांग रहे हैं? – Triptych
नहीं, एक प्रारंभिक रूप से यादृच्छिक रूप से आदेशित सूची –
मुझे अभी भी सवाल नहीं मिला है, क्षमा करें। "यादृच्छिक रूप से आदेश दिया गया" से आपका क्या मतलब है? और यदि परिणाम सॉर्ट किया जाना चाहिए, तो आपके पास कई संभावित परिणाम क्यों हैं (जो मेरे लिए हैं, वास्तव में बिल्कुल हल नहीं किए गए हैं)? क्या एक और लंबा उदाहरण संभव है? – Kosi2801