मनुष्यों द्वारा किए गए तुलना के लिए सॉर्टिंग एल्गोरिदम सूची

Question

इस प्रश्न को एक बार पहले पूछा गया था लेकिन उत्तर नहीं दिया गया था इसलिए मैंने सोचा कि मैं अपनी स्थिति में कुछ विशिष्टताओं के साथ फिर से पूछूंगा।

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

मुद्दा यह है कि परंपरागत रूप से क्रमबद्ध रणनीतियों, कोई फर्क नहीं पड़ता कितनी तेजी से संभव है एक मानव समय (यहां तक ​​कि 50 जितनी कम एक सूची के साथ के किसी भी समझदार राशि में करने के लिए, के रूप में आवश्यक रूप से अधिक कार्य शामिल करने के लिए जा रहे हैं मेरे वर्तमान परीक्षण सूची है)।

स्पष्ट रूप से कम पर्याप्त जटिलता वाले गारंटीकृत सॉर्टिंग एल्गोरिदम नहीं है, मुझे लगता है कि कुछ भत्ते किए गए हैं। सॉर्टिंग के बड़े हिस्से को छोड़ने का कोई तरीका है? मैंने उन चीज़ों की संख्या के आधार पर वस्तुओं को मूल्य निर्दिष्ट करने का कुछ तरीका माना जो उन्होंने 'जीते' हैं और फिर थोड़ी देर के बाद सॉर्ट को रोकते हुए मानते हैं कि ये मान सही क्रम देते हैं, शैली के समान जो आप स्विस शतरंज को हल कर सकते हैं टूर्नामेंट यदि आप आमतौर पर विजेता को निर्धारित करने के लिए पर्याप्त राउंड पूरा नहीं कर सकते हैं। मुझे नहीं पता कि यह व्यवहार्य है या नहीं।

एक उदाहरण स्पष्ट करने के लिए मैं क्या मतलब है: कहते हैं कि तुम

Apple 
Orange 
Kiwi 
Banana 
Melon 

की एक सूची यह आप जब तक आप एक सूची है कि तरह दिखता है जैसे

Do you prefer: 
A Apple 
B Kiwi 

तुलना की पेशकश और इतने पर होता था

Kiwi 
Apple 
Orange 
Melon 
Banana 

जो कि फल के वरीयता का आपका आदेश है।

Answer 1

आपकी फल प्राथमिकताएं क्या हैं? क्या आपके दिमाग में वरीयताओं की पूर्ण आदेश वाली सूची है, या क्या आपके पास "अधिक से अधिक की तरह" फल हैं, जो फल आप "सबसे कम से कम" हैं, और बाकी जिनके बारे में आपके पास कोई मजबूत भावना नहीं है - या आपने कोशिश भी नहीं की है।

आपकी समस्या को तैयार करने के तरीके में समस्या यह है कि आपने माना है कि एक व्यक्ति की प्राथमिकता total order है, जिसे स्वाभाविक रूप से सूची के रूप में एन्कोड किया गया है। असल में, एक व्यक्ति की वरीयताएं अक्सर partial order होती हैं, जो स्वाभाविक रूप से directed acyclic graph के रूप में एन्कोड की जाती है।

उदाहरण के लिए, फल {Apple, Orange, Kiwi, Banana, Melon, Starfruit} के सेट के लिए, मैं फल वरीयताओं के रूप में निम्नानुसार हो सकता है:

Melon < Apple 
Apple < Banana 
Banana < Kiwi 
Banana < Orange 

एक अच्छा एक आंशिक उपयोगकर्ता इनपुट के आधार पर आदेश पर पहुंचने के लिए जिस तरह से radix sort नकल करने के लिए है। शुरू करने के लिए, उपयोगकर्ता को प्रत्येक फल के लिए चुनने के लिए कहें, चाहे वे इसे पसंद करते हैं, इसे नापसंद करते हैं, इसके बारे में तटस्थ महसूस करते हैं, या नहीं जानते। मुझे लगता है कि जवाब देने देंगी:

  Like Dislike Neutral Unknown 
Apple     x 
Orange  x 
Kiwi  x 
Banana  x 
Melon   x 
Starfruit      x 

Dislike < Neutral < Like मानते हुए, इन उत्तरों निम्न जानकारी सांकेतिक शब्दों में बदलना है, भले ही मैं केवल के रूप में कई सवाल का उत्तर दिया है के रूप में वहाँ फल हैं:

Melon < Apple 
Apple < Orange 
Apple < Kiwi 
Apple < Banana 

इसके बाद, पहचान जो उत्तर (ओं) को सबसे अधिक चेक अंक प्राप्त हुए। इस मामले में, मैं, मुझे पसंद है 3 फल के लिए 1 मैं नापसंद करते हैं, और 1 के बारे में मैं तटस्थ लग रहा है लगता है (जब तक कि मूंगफली का मक्खन शामिल होता है), और 1 मैं कभी नहीं की कोशिश की है (इसलिए मैं के संबंध में कोई वरीयता नहीं है अन्य फल)।

तो प्राकृतिक स्थान पर आगे मेरी प्राथमिकताओं की जांच के लिए फल मुझे पसंद है भीतर होगा। समस्या रिकर्सिव है: अब आप फल {Orange, Kiwi, Banana} के सेट में अपनी वरीयताओं को निर्धारित करना चाहते हैं। तुम मुझे पूछ सकते जो उन फलों की मेरी पसंदीदा हैं, और मैं क्लिक करेंगे Orange और Kiwi। यही कारण है कि आपको बताता है निम्नलिखित:

Banana < Orange 
Banana < Kiwi 

जानकारी के पहले दौर के साथ संयुक्त, आप अब:

Melon < Apple 
Apple < Orange 
Apple < Kiwi 
Apple < Banana 
Banana < Kiwi 
Banana < Orange 

Apple < Banana और Banana < Kiwi मतलब Apple < Kiwi; Apple < Banana और Banana < OrangeApple < Orange मतलब।

Melon < Apple 
Apple < Banana 
Banana < Kiwi 
Banana < Orange 

Answer 2

आप उपयोगकर्ता को न केवल यह बता सकते हैं कि कोई आइटम किसी अन्य से अधिक बेहतर है या नहीं, लेकिन 1 से 10 तक की रेटिंग भी उदाहरण के लिए वह एक दूसरे से कितना पसंद करता है। इस तरह आपके पास अधिक जानकारी है और आसानी से रैंकिंग बना सकते हैं।

इष्टतम दृष्टिकोण में जहां उपयोगकर्ता केवल छोटे या बड़े कह सकता है, आपको सूची में प्रत्येक आइटम के लिए बाइनरी खोज करने की आवश्यकता है। बाइनरी खोज में जटिलता O(log n) है। n बार n के साथ 1 से n पर जाकर कुल O(n * log (n/2)) बनाता है। 50 वस्तुओं के मामले में जो 200 से अधिक चरणों की आवश्यकता होगी।

Answer 3

insertion sort का उपयोग करें। उपयोगकर्ता को एक समय में दो वस्तुओं की तुलना करने के लिए कहने के बजाय, उन्हें अपनी शेष सूची को शेष सूची से चुनने के लिए कहें। उस आइटम को क्रमबद्ध सूची के अंत में रखें, इसे शेष वस्तुओं से हटा दें, और शेष आइटम समाप्त होने तक दोहराएं।