तुलना आधारित सॉर्टिंग तकनीकों की सीमाएं

Question

तुलनात्मक क्रम का चयन उन अधिकांश परिदृश्यों में किया जाता है जहां डेटा को आदेश देने की आवश्यकता होती है। मर्ज सॉर्ट, त्वरित सॉर्ट, सम्मिलन सॉर्ट और अन्य तुलनात्मक प्रकार जैसी तकनीकें O (nLog (n)) की निचली सीमा के साथ विभिन्न डेटा प्रकारों और दक्षता को संभाल सकती हैं।

मेरे सवाल कर रहे हैं

1. वहाँ हैं आधारित तुलना की कोई सीमाएं तकनीक छँटाई?
2. किसी भी प्रकार के परिदृश्य जहां गैर तुलनात्मक सॉर्टिंग तकनीकों का उपयोग किया जाएगा?

चियर्स

Answer 1

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

Pigeonhole sort एक महान और काफी सरल उदाहरण है जो तब तक बहुत तेज है जब तक संभावित कुंजी मानों की संख्या तत्वों की संख्या के करीब है।

Answer 2

जाहिर है तुलनात्मक प्रकार की सीमाएं समय कारक - some are better than others है, लेकिन एक बड़ा पर्याप्त डेटा सेट दिया गया है, वे सभी बिंदु पर बहुत धीमे हो जाएंगे। यह चाल सही प्रकार का चयन करने और आपके द्वारा क्रमबद्ध डेटा के मिश्रण को चुनने का है।

गैर तुलनात्मक सॉर्टिंग डेटा को अनदेखा करने वाले अन्य कारकों पर आधारित है, उदाहरण के लिए counting sort प्रत्येक तत्व का निरीक्षण करके डेटा संग्रह का ऑर्डर करेगा - संग्रह में किसी भी अन्य मूल्य के साथ तुलना नहीं कर रहा है। गिनती सॉर्ट कुछ डेटा के आधार पर संग्रह को ऑर्डर करने के लिए उपयोगी होता है, यदि आपके पास पूर्णांक का संग्रह होता है, तो यह सभी तत्वों को 1 के मान के साथ ले जाकर उन्हें पहले गंतव्य में डालकर ऑर्डर करेगा, फिर मूल्य 2 के सभी तत्व (ठीक है, यह संग्रह के माध्यम से ज़ूम करने और मूल्यों को पुन: व्यवस्थित करने के लिए "स्पैस" सरणी का उपयोग करता है, अंतराल को छोड़कर, लेकिन यह मूल सिद्धांत है)

Answer 3

यह देखना आसान है, तुलनात्मक प्रकार को एन लॉग एन तुलनाओं के बारे में क्यों आवश्यकता है। वहां नहीं! क्रमपरिवर्तन और जैसा कि हम जानते हैं कि एलएन (एन!) लगभग एन एलएन एन - एन + ओ (एलएन एन) है। बड़े ओ नोटेशन में, हम एन एलएन एन से कम शर्तों को अनदेखा कर सकते हैं, और क्योंकि एलएन और लॉग केवल स्थिरता से भिन्न होते हैं, हमें अंतिम परिणाम ओ (एन लॉग एन)

मिलता है