सम्मिलन प्रकार बबल प्रकार से बेहतर है?

Question

मैं परीक्षा के लिए अपना संशोधन कर रहा हूं।

क्या जानना चाहेंगे कि सम्मिलन क्रम में बबल प्रकार से बेहतर प्रदर्शन होता है, ओ (एन^2) की औसत औसत जटिलता दी जाती है।

मुझे कुछ संबंधित लेख मिले, लेकिन मैं उन्हें समझ नहीं पाया।

क्या कोई इसे सरल तरीके से समझाएगा?

Answer 1

मुझे लगता है कि इस सवाल का जवाब आप देख रहे हैं here है:

बुलबुला तरह भी कुशलता से एक सूची पहले से ही है कि तत्वों का एक बहुत छोटी संख्या के अलावा अनुसार क्रमबद्ध पर इस्तेमाल किया जा सकता है। उदाहरण के लिए, यदि केवल एक तत्व क्रम में नहीं है, तो बबल प्रकार में केवल 2 एन समय लगेगा। दो तत्वों क्रम में नहीं हैं पर, बबल तरह केवल ज्यादा से ज्यादा 3n समय

और

निवेशन तरह ले जाएगा ... एक सरल छंटाई एल्गोरिथ्म है कि अपेक्षाकृत छोटे सूचियों के लिए कुशल है और ज्यादातर सूचियों अनुसार क्रमबद्ध हैं, और अक्सर अधिक परिष्कृत एल्गोरिदम

Answer 2

bubblesort का लाभ एक पहले से ही sorte का पता लगाने की गति में है के भाग के रूप में किया जाता है घ सूची:

BubbleSort बेस्ट मामले परिदृश्य: O (n)

हालांकि, यहां तक ​​कि इस मामले प्रविष्टि में तरह बेहतर/एक ही प्रदर्शन मिला है।

Bubblesort, कम या ज्यादा, समझ और/या sortalgorithm के तंत्र को पढ़ाने के लिए केवल अच्छा है, लेकिन अभ्यस्त इन दिनों प्रोग्रामिंग में एक समुचित उपयोग मिल जाए, क्योंकि इसकी जटिलता

ओ (n²)

का अर्थ है कि इसकी दक्षता तत्वों की एक छोटी संख्या से अधिक की सूचियों पर नाटकीय रूप से कम हो जाती है।

Answer 3

निम्नलिखित बातें मेरे दिमाग में आया था:

1. बुलबुला तरह हमेशा निर्धारित करने के लिए अगर यह हल कर रहा है सरणी पर एक और पास ले जाता है। दूसरी तरफ, सम्मिलन क्रम की आवश्यकता नहीं है - एक बार अंतिम तत्व डालने के बाद, एल्गोरिदम गारंटी देता है कि सरणी क्रमबद्ध है।

2. बबल सॉर्ट n प्रत्येक पास पर तुलना करता है। सम्मिलन क्रम n तुलना से कम करता है: एक बार एल्गोरिदम को उस स्थिति को पाता है जहां वर्तमान तत्व डालना है, यह तुलना करने से रोकता है और अगला तत्व लेता है।

3. अंत में, wikipedia लेख से बोली:

बुलबुला तरह भी खराब आधुनिक सीपीयू हार्डवेयर के साथ सूचना का आदान प्रदान। यह को सम्मिलन क्रम के रूप में कम से कम दो बार लिखने की आवश्यकता होती है, के रूप में दो बार कई कैश याद आती हैं, और असम्बद्ध रूप से अधिक शाखा गलतफहमी। प्रयोगों एस्ट्राकेन जावा में तार छँटाई के द्वारा दिखाने को बुलबुला प्रकार प्रविष्टि तरह से मोटे तौर पर 5 गुना धीमी और 40% चयन की तुलना में धीमी तरह

आप मूल शोध पत्र के लिए लिंक मिल सकता है हो सकता है।

Answer 4

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

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

कहा जा रहा है, इसे नमक के अनाज के साथ ले जाएं। सबसे पहले, सॉर्टिंग सरणी, व्यावहारिक रूप से, लिंक्ड सूचियों को सॉर्ट करने से लगभग हमेशा तेज होती है। बस इस तथ्य के कारण कि सूची स्कैन करने से पहले एक बड़ा अंतर होता है। इसके अलावा, दाईं ओर एक सरणी के एन तत्वों को स्थानांतरित करना, एन (या यहां तक ​​कि n/2) स्वैप करने से बहुत तेज़ है। यही कारण है कि अन्य उत्तरों सामान्य रूप से सम्मिलन प्रकार का दावा सामान्य रूप से बेहतर मानते हैं, और मैं वास्तव में आपके द्वारा पढ़े गए लेखों के बारे में क्यों सोचता हूं, क्योंकि मैं यह कहने का एक आसान तरीका सोचने में असफल रहता हूं कि यह मामलों ए में बेहतर है, और यह मामलों में बेहतर है बी