इनसेट सॉर्ट: एल्गोरिथम कैसे काम करता है इसके उदाहरण

2024 लेखक: Angel Austin | [email protected]. अंतिम बार संशोधित: 2024-02-02 15:35

किसी सरणी को छांटने की समस्या को हल करने के लिए कई बुनियादी एल्गोरिदम हैं। उनमें से सबसे प्रसिद्ध में से एक सम्मिलन प्रकार है। इसकी स्पष्टता और सरलता, लेकिन कम दक्षता के कारण, इस पद्धति का उपयोग मुख्य रूप से प्रोग्रामिंग सिखाने में किया जाता है। यह आपको बुनियादी छँटाई तंत्र को समझने की अनुमति देता है।

एल्गोरिदम का विवरण

सम्मिलन सॉर्ट एल्गोरिथ्म का सार यह है कि प्रारंभिक सरणी के अंदर एक उचित क्रमित खंड बनता है। प्रत्येक तत्व की एक-एक करके जाँच किए गए भाग से तुलना की जाती है और सही जगह पर डाला जाता है। इस प्रकार, सभी तत्वों के माध्यम से पुनरावृति करने के बाद, वे सही क्रम में पंक्तिबद्ध हो जाते हैं।

तत्वों के चयन का क्रम कोई भी हो सकता है, उन्हें मनमाने ढंग से या किसी एल्गोरिथम के अनुसार चुना जा सकता है। अक्सर, अनुक्रमिक गणना का उपयोग सरणी की शुरुआत से किया जाता है, जहां एक आदेशित खंड बनता है।

सॉर्टिंग की शुरुआत कुछ इस तरह दिख सकती है:

1. सरणी का पहला तत्व लें।
2. चूंकि इसकी तुलना करने के लिए कुछ भी नहीं है, तत्व को स्वयं आदेश के अनुसार लेंअनुक्रम।
3. दूसरे आइटम पर जाएं।
4. सॉर्ट नियम के आधार पर इसकी तुलना पहले वाले से करें।
5. यदि आवश्यक हो, तत्वों को स्थानों में स्वैप करें।
6. पहले दो तत्वों को एक क्रमबद्ध क्रम के रूप में लें।
7. तीसरे आइटम पर जाएं।
8. इसकी तुलना दूसरे से करें, यदि आवश्यक हो तो स्वैप करें।
9. यदि प्रतिस्थापन किया जाता है, तो इसकी तुलना पहले वाले से करें।
10. तीन तत्वों को एक क्रमबद्ध क्रम के रूप में लें।

और इसी तरह मूल सरणी के अंत तक।

रियल लाइफ इंसर्शन सॉर्ट

स्पष्टता के लिए, यह उदाहरण देने योग्य है कि कैसे इस छँटाई तंत्र का उपयोग रोजमर्रा की जिंदगी में किया जाता है।

उदाहरण के लिए, एक बटुआ लें। सौ, पांच सौ और हजार डॉलर के बिल बैंकनोट डिब्बे में अव्यवस्थित हैं। यह एक गड़बड़ है, ऐसे हौज में कागज का सही टुकड़ा तुरंत खोजना मुश्किल है। बैंकनोटों की सरणी को क्रमबद्ध किया जाना चाहिए।

सबसे पहले 1000 रूबल का बैंकनोट है, और इसके तुरंत बाद - 100। हम एक सौ लेते हैं और इसे सामने रखते हैं। एक पंक्ति में तीसरा 500 रूबल है, इसके लिए सही जगह एक सौ एक हजार के बीच है।

इसी तरह हम "मूर्ख" खेलते समय प्राप्त कार्डों को क्रमबद्ध करते हैं ताकि उन्हें नेविगेट करना आसान हो सके।

ऑपरेटर और सहायक कार्य

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

पहला तत्व अपने आप में एक क्रमित सेट है, इसलिए तुलना दूसरे से शुरू होती है।

एल्गोरिदम अक्सर दो मानों (स्वैप) का आदान-प्रदान करने के लिए एक सहायक फ़ंक्शन का उपयोग करता है। यह एक अतिरिक्त अस्थायी चर का उपयोग करता है, जो स्मृति की खपत करता है और कोड को थोड़ा धीमा कर देता है।

एक विकल्प यह है कि तत्वों के समूह को बड़े पैमाने पर स्थानांतरित किया जाए और फिर वर्तमान को खाली स्थान में डाला जाए। इस मामले में, अगले तत्व में संक्रमण तब होता है जब तुलना ने सकारात्मक परिणाम दिया, जो सही क्रम को इंगित करता है।

कार्यान्वयन उदाहरण

विशिष्ट कार्यान्वयन काफी हद तक उपयोग की जाने वाली प्रोग्रामिंग भाषा, उसके सिंटैक्स और संरचनाओं पर निर्भर करता है।

अस्थायी चर का उपयोग करके मूल्यों का आदान-प्रदान करने के लिए क्लासिक सी कार्यान्वयन:

इंट आई, जे, टेम्प; के लिए (i=1; मैं =0; j--) { अगर (सरणी [जे] < अस्थायी) तोड़; सरणी [जे + 1]=सरणी [जे]; सरणी [जे]=अस्थायी; } }








PHP कार्यान्वयन:


फ़ंक्शन सम्मिलन_सॉर्ट(&$a) { के लिए ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ जे + 1]=$ ए [$ जे]; } $a[$j + 1]=$x; } }

यहां, सबसे पहले, सभी तत्व जो सॉर्ट की स्थिति से मेल नहीं खाते हैं, उन्हें दाईं ओर स्थानांतरित कर दिया जाता है, और फिर वर्तमान तत्व को खाली स्थान में डाला जाता है।
जब लूप का उपयोग कर जावा कोड:


सार्वजनिक स्थैतिक शून्य सम्मिलन सॉर्ट (int गिरफ्तारी) { के लिए (int i=1; i =0 && arr [prevKey] > currElem){ arr[prevKey+1]=गिरफ्तारी [prevKey]; गिरफ्तारी [prevKey]=currElem; पिछलाकी--; } } }

कोड का सामान्य अर्थ अपरिवर्तित रहता है: सरणी के प्रत्येक तत्व की क्रमिक रूप से पिछले वाले के साथ तुलना की जाती है और यदि आवश्यक हो तो उनके साथ अदला-बदली की जाती है।

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







सबसे खराब स्थिति इनपुट एक सरणी है जिसे उल्टे क्रम में क्रमबद्ध किया गया है। इसके लिए बड़ी संख्या में क्रमपरिवर्तन की आवश्यकता होगी, रनटाइम फ़ंक्शन वर्ग तत्वों की संख्या पर निर्भर करेगा।
एक पूरी तरह से अव्यवस्थित सरणी के लिए क्रमपरिवर्तन की सटीक संख्या की गणना सूत्र का उपयोग करके की जा सकती है:


n(n-1)/2

जहां n मूल सरणी की लंबाई है। इस प्रकार, 100 तत्वों को सही क्रम में व्यवस्थित करने के लिए 4950 क्रमपरिवर्तनों की आवश्यकता होगी।
सम्मिलन विधि छोटे या आंशिक रूप से क्रमबद्ध सरणियों को छाँटने के लिए बहुत कुशल है। हालांकि, गणना की उच्च जटिलता के कारण इसे हर जगह लागू करने की अनुशंसा नहीं की जाती है।
एल्गोरिदम का उपयोग कई अन्य जटिल छँटाई विधियों में सहायक के रूप में किया जाता है।






समान मानों को क्रमबद्ध करें
सम्मिलन एल्गोरिथ्म तथाकथित स्थिर प्रकारों से संबंधित है। इसका मतलब,कि यह समान तत्वों की अदला-बदली नहीं करता, बल्कि उनके मूल क्रम को बनाए रखता है। स्थिरता सूचकांक कई मामलों में सही क्रम के लिए महत्वपूर्ण है।





उपरोक्त एक नृत्य में सम्मिलन प्रकार का एक बेहतरीन दृश्य उदाहरण है।