कंप्यूटर विज्ञान सभी एल्गोरिदम और डेटा संरचनाओं की जटिलताओं को समझने के बारे में है।
आपके पास आइटम की एक सूची है जिसे सॉर्ट करने की आवश्यकता है, लेकिन आपके पास अधिक जटिल सॉर्टिंग एल्गोरिदम का उपयोग करने के लिए समय या संसाधन नहीं है।
सम्मिलन छँटाई सबसे सरल छँटाई एल्गोरिदम में से एक है, लेकिन यह बड़ी सूचियों के लिए धीमा हो सकता है।
आसान कार्यान्वयन और समझ ने इस पद्धति को प्रोग्रामर्स के बीच पसंदीदा बना दिया है। यह छोटी सूचियों के लिए या जब आपको त्वरित समाधान की आवश्यकता हो, तो यह एकदम सही है।
इस ब्लॉग पोस्ट में, हम सम्मिलन छँटाई की समय जटिलता को देखेंगे। इस एल्गोरिथ्म का उपयोग सरणियों को सॉर्ट करने के लिए किया जाता है, और इसमें O(n .) का रनटाइम होता है2) इसका मतलब है कि सरणी के आकार के साथ समय की जटिलता बढ़ जाती है।
हालांकि, यह एल्गोरिथम अन्य सॉर्टिंग एल्गोरिदम की तुलना में अक्सर तेज हो सकता है, जैसे कि क्विकॉर्ट।
आइए देखें कि सम्मिलन छँटाई कैसे काम करती है!
इंसर्शन सॉर्ट एल्गोरिथम क्या है?
एक समय में एक तत्व, सम्मिलन क्रम एक क्रमबद्ध सरणी उत्पन्न करता है, जिसे अक्सर एक सूची कहा जाता है।
उदाहरण के लिए, छँटाई जटिल कंप्यूटर प्रोग्राम जैसे कंपाइलर में लागू होती है, जहाँ प्रोग्राम की व्याख्या के लिए टोकन का क्रम महत्वपूर्ण होता है।
इंसर्शन सॉर्ट कैसे काम करता है?
जब हम किसी ऐरे को सॉर्ट करने के लिए इंसर्शन सॉर्ट का उपयोग करते हैं, तो एल्गोरिथम सूची में सबसे छोटी वस्तु को खोजने और उसे सही स्थिति में डालने से शुरू होता है।
इसके बाद यह अगली सबसे छोटी वस्तु ढूंढता है और उसे सही स्थिति में डालता है, और इसी तरह।
एल्गोरिथ्म सूची के माध्यम से लूप करके काम करता है, प्रत्येक आइटम की तुलना उसके सामने आने वाले से करता है।
यदि आइटम गलत क्रम में हैं, तो एल्गोरिथम उन्हें स्वैप कर देता है। फिर यह देखने के लिए जाँच करता है कि क्या सूची को क्रमबद्ध किया गया है, और यदि यह है, तो एल्गोरिथ्म समाप्त हो जाता है।
व्यवहार में, सम्मिलन क्रम को अक्सर कोड की कुछ पंक्तियों का उपयोग करके कार्यान्वित किया जाता है, जिससे यह छोटे सरणियों को छांटने के लिए एक लोकप्रिय विकल्प बन जाता है। हालांकि, इस एल्गोरिदम का उपयोग करते समय समय जटिलता पर विचार किया जाना चाहिए।
उदाहरण:
यहां एक उदाहरण दिया गया है कि सम्मिलन छँटाई कैसे काम करती है। हम निम्नलिखित सरणी का उपयोग करेंगे:
1, 2, 3 4, 5, 6
एल्गोरिथ्म सूची में सबसे छोटी वस्तु को खोजने से शुरू होता है, जो कि 1 है। यह फिर इसे सही स्थिति, पहली स्थिति में सम्मिलित करता है। इसके बाद यह अगला सबसे छोटा आइटम ढूंढता है, जो कि 2 है। यह इसे सही स्थिति में सम्मिलित करता है, जो कि दूसरी स्थिति है।
इसके बाद यह अगला सबसे छोटा आइटम ढूंढता है, जो कि 3 है। यह इसे सही स्थिति में सम्मिलित करता है, जो कि तीसरी स्थिति है।
इसके बाद यह अगला सबसे छोटा आइटम ढूंढता है, जो कि 4 है। यह इसे सही स्थिति में डालता है, जो चौथी स्थिति है, और इसी तरह। सूची अब क्रमबद्ध है!
हम उदाहरण से देख सकते हैं कि एल्गोरिथ्म छह तुलनाओं को लेता है और सूची को क्रमबद्ध करने के लिए स्वैप करता है। ऐसा इसलिए है क्योंकि यह n . लेता है2 तुलना और स्वैप n वस्तुओं की सूची को सॉर्ट करने के लिए। इस मामले में, एन = 6।
इंसर्शन सॉर्ट टाइम कॉम्प्लेक्सिटी में सुधार कैसे करें?
जबकि सम्मिलन क्रम में ओ (एन .) का रनटाइम होता है2), इसे बेहतर सॉर्टिंग एल्गोरिथम का उपयोग करके बेहतर बनाया जा सकता है, जैसे कि क्विकॉर्ट।
क्विकॉर्ट में ओ (एन लॉग एन) रनटाइम है, जो ओ (एन .) से बहुत तेज है2).
हालांकि, कुछ मामलों में, सम्मिलन छँटाई क्विकसॉर्ट की तुलना में तेज़ हो सकती है।
उदाहरण के लिए, यदि सूची पहले से ही क्रम में है, तो सम्मिलन छँटाई में क्विकॉर्ट की तुलना में कम समय लगेगा।
व्यवहार में, सम्मिलन क्रम को अक्सर कोड की कुछ पंक्तियों का उपयोग करके कार्यान्वित किया जाता है, जिससे यह छोटे सरणियों को छांटने के लिए एक लोकप्रिय विकल्प बन जाता है।
हालांकि, इस एल्गोरिदम का उपयोग करते समय समय जटिलता पर विचार किया जाना चाहिए।
समय की जटिलताएं
सबसे खराब स्थिति जटिलता हे (एन2):
सरणी के आकार के साथ समय जटिलता बढ़ जाती है। यह नहीं लेता है2 तुलना और स्वैप n वस्तुओं की सूची को सॉर्ट करने के लिए।
उदाहरण के लिए, यदि हमारे पास आकार 1000 की एक सरणी है, तो एल्गोरिथ्म 1,000,000 तुलनाओं को लेगा और सरणी को क्रमबद्ध करने के लिए स्वैप करेगा।
बेस्ट केस कॉम्प्लेक्सिटी ओ (एन):
समय जटिलता इनपुट सरणी के आकार के समान है। मैं
t n तुलना करता है और n आइटम की सूची को सॉर्ट करने के लिए स्वैप करता है। उदाहरण के लिए, आकार 5 की एक सरणी पर विचार करें। एल्गोरिथ्म पांच तुलनाओं को लेगा और सरणी को क्रमबद्ध करने के लिए स्वैप करेगा।
औसत केस जटिलता हे (एन2):
इस मामले में समय की जटिलता सबसे खराब और सबसे अच्छी स्थिति की जटिलताओं के बीच है।
यह नहीं लेता है2 तुलना और स्वैप n वस्तुओं की सूची को सॉर्ट करने के लिए।
इस प्रकार, सम्मिलन छँटाई एक स्थिर छँटाई एल्गोरिथ्म है।
इंसर्शन सॉर्ट स्थिर क्यों है?
सम्मिलन क्रम स्थिर है क्योंकि यह इनपुट सरणी में समान तत्वों के क्रम को संरक्षित करता है।
यह कई अनुप्रयोगों के लिए महत्वपूर्ण है, जैसे डेटा पुनर्प्राप्ति या वित्तीय विश्लेषण। उदाहरण के लिए, यदि हमारे पास संख्याओं की दो सूचियाँ हैं और उनकी तुलना करना चाहते हैं, तो हमें यह सुनिश्चित करने की आवश्यकता है कि तत्वों का क्रम संरक्षित है।
यदि सूचियों को क्रमबद्ध नहीं किया जाता है, तो हम उनकी सही तुलना नहीं करेंगे।
एक जवाब लिखें