वहां बड़ी संख्या में सॉर्टिंग एल्गोरिदम हैं, लेकिन उनमें से अधिकांश केवल पूरी तरह से आदेशित सेट पर काम करते हैं क्योंकि वे मानते हैं कि किसी भी दो तत्व तुलनीय हैं। हालांकि, क्या पॉज़ सॉर्ट करने के लिए वहां कोई अच्छा एल्गोरिदम है, जहां कुछ तत्व अतुलनीय हैं? एक आदेश यही है, तत्वों का एक सेट एस एक poset से तैयार को देखते हुए उत्पादन के लिए सबसे अच्छा तरीका क्या है एक्स , एक्स , ..., एक्स n ऐसी है कि अगर एक्स मैं ≤ एक्स जे, i ≤ जे?एक पॉकेट छंटनी?
arxiv.org पर Sorting and Selection in Posets शीर्षक वाला एक पेपर है जो ऑर्डर ओ ((डब्ल्यू^2) एनएलओ (एन/डब्ल्यू)) के सॉर्टिंग विधियों पर चर्चा करता है, जहां पॉकेट की "चौड़ाई" है। मैंने पेपर नहीं पढ़ा है, लेकिन ऐसा लगता है जैसे आप इसे ढूंढ रहे हैं।
लिंक के लिए धन्यवाद! यह बहुत ही आशाजनक लग रहा है! – templatetypedef
मैं चयन-विनिमय प्रकार से शुरू करूंगा। वह ओ (एन^2) है और मुझे नहीं लगता कि आप इससे बेहतर प्रदर्शन करेंगे।
Topological sort आंशिक रूप से आदेशित सेट को सॉर्ट करने के लिए उपयुक्त है। अधिकांश एल्गोरिदम ओ (एन^2) हैं। यहाँ विकिपीडिया से एक एल्गोरिथ्म है:
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
add n to tail of L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
एक helpful video example नहीं है। अधिकांश यूनिक्स-जैसी प्रणालियों में tsort कमांड है। आप tsort के साथ वीडियो के ब्राउनी उदाहरण को हल कर सकते हैं:
$ cat brownies.txt
preheat bake
water mix
dry_ingredients mix
grease pour
mix pour
pour bake
$ tsort brownies.txt
grease
dry_ingredients
water
preheat
mix
pour
bake
क्या यह सिर्फ स्थलीय प्रकार नहीं है? –
@ jleedev- आप इसे केवल एक स्थलीय प्रकार के साथ कर सकते हैं अगर आपको पता था कि एस में तत्वों की प्रत्येक जोड़ी एक दूसरे के साथ तुलना की जाती है; अन्यथा आपको सभी तुलना करने के लिए ओ (| एस |^2) समय बिताना होगा। – templatetypedef