सम्मिलन क्रमबद्ध समय जटिलता

निम्नलिखित संख्याओं पर विचार करें:

50 60 30 10 80 70 20 40

यदि इस सूची को आरोही क्रम में क्रमबद्ध किया जाता है, तो यह होगा:

10 20 30 40 50 60 70 80

यदि इसे अवरोही क्रम में क्रमबद्ध किया जाता है, तो यह होगा:

80 70 60 50 40 30 20 10

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

सम्मिलन क्रमबद्ध करने के लिए एल्गोरिथम

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

• • सूची को शुरू से ही स्कैन किया जाता है।
  • जबकि स्कैनिंग चल रही है, अपने पूर्ववर्ती से कम किसी भी संख्या को अपने पूर्ववर्ती के साथ बदल दिया जाता है।
  • यह अदला-बदली सूची के साथ तब तक जारी रहती है, जब तक कि अदला-बदली करना संभव नहीं रह जाता।
  • जब स्कैनिंग अंत तक पहुँच जाती है, तो छँटाई पूरी हो जाती है।

सम्मिलन क्रमबद्ध चित्रण

समय जटिलता से निपटने के दौरान, यह सबसे खराब स्थिति है जिसे आम तौर पर ध्यान में रखा जाता है। पिछली सूची के लिए सबसे खराब व्यवस्था है:

80 70 60 50 40 30 20 10

शून्य से 7 तक के सूचकांक वाले आठ तत्व हैं।

सूचकांक शून्य पर, स्कैनिंग 80 हो जाती है। यह एक आंदोलन है। यह एक आंदोलन एक ऑपरेशन है। अब तक कुल एक ऑपरेशन हुआ है (एक आंदोलन, कोई तुलना नहीं, और कोई स्वैप नहीं)। परिणाम है:

| 80 70 60 50 40 30 20 10

सूचकांक एक पर, 70 की गति होती है। 70 की तुलना 80 से की जाती है। 70 और 80 की अदला-बदली की जाती है। एक आंदोलन एक ऑपरेशन है। एक तुलना भी एक ऑपरेशन है। एक स्वैप भी एक ऑपरेशन है। यह खंड तीन ऑपरेशन प्रदान करता है। अब तक कुल चार ऑपरेशन हुए हैं (1 + 3 = 4)। परिणाम इस प्रकार है:

70 | 80 60 50 40 30 20 10

सूचकांक दो पर, 60 की गति होती है। 60 की तुलना 80 से की जाती है, फिर 60 और 80 की अदला-बदली की जाती है। 60 की तुलना 70 से की जाती है, फिर 60 और 70 की अदला-बदली की जाती है। एक आंदोलन एक ऑपरेशन है। दो तुलना दो ऑपरेशन हैं। दो स्वैप दो ऑपरेशन हैं। यह खंड पांच ऑपरेशन प्रदान करता है। अब तक कुल नौ ऑपरेशन हो चुके हैं (4 + 5 = 9)। परिणाम इस प्रकार है:

60 70 | 80 50 40 30 20 10

सूचकांक तीन पर, 50 की गति होती है। 50 की तुलना 80 से की जाती है, फिर 50 और 80 की अदला-बदली की जाती है। 50 की तुलना 70 से की जाती है, फिर 50 और 70 की अदला-बदली की जाती है। 50 की तुलना 60 से की जाती है, फिर 50 और 60 की अदला-बदली की जाती है। एक आंदोलन एक ऑपरेशन है। तीन तुलना तीन ऑपरेशन हैं। तीन स्वैप तीन ऑपरेशन हैं। यह खंड सात ऑपरेशन प्रदान करता है। अब तक कुल सोलह ऑपरेशन हो चुके हैं (9 + 7 = 16)। परिणाम इस प्रकार है:

50 60 70 | 80 40 30 20 10

सूचकांक चार पर, 40 की गति होती है। 40 की तुलना 80 से की जाती है, फिर 40 और 80 की अदला-बदली की जाती है। 40 की तुलना 70 से की जाती है, फिर 40 और 70 की अदला-बदली की जाती है। 40 की तुलना 60 से की जाती है, फिर 40 और 60 की अदला-बदली की जाती है। 40 की तुलना 50 से की जाती है, फिर 40 और 50 की अदला-बदली की जाती है। एक आंदोलन एक ऑपरेशन है। चार तुलना चार ऑपरेशन हैं। चार स्वैप चार ऑपरेशन हैं। यह खंड नौ ऑपरेशन प्रदान करता है। अब तक कुल पच्चीस ऑपरेशन हो चुके हैं (16 + 9 = 25)। परिणाम इस प्रकार है:

40 50 60 70 80 | 30 20 10

सूचकांक पांच पर, 30 की गति होती है। 30 की तुलना 80 से की जाती है, फिर 30 और 80 की अदला-बदली की जाती है। 30 की तुलना 70 से की जाती है, फिर 30 और 70 की अदला-बदली की जाती है। 30 की तुलना 60 से की जाती है, फिर 30 और 60 की अदला-बदली की जाती है। 30 की तुलना 50 से की जाती है, फिर 30 और 50 की अदला-बदली की जाती है। 30 की तुलना 40 से की जाती है, फिर 30 और 40 की अदला-बदली की जाती है। एक आंदोलन एक ऑपरेशन है। पाँच तुलनाएँ पाँच ऑपरेशन हैं। पांच स्वैप पांच ऑपरेशन हैं। यह खंड ग्यारह संचालन प्रदान करता है। अब तक कुल छत्तीस ऑपरेशन हो चुके हैं (25 + 11 = 36)। परिणाम इस प्रकार है:

30 40 50 60 70 80 | 20 10

सूचकांक छह पर, 20 की गति होती है। 20 की तुलना 80 से की जाती है, फिर 20 और 80 की अदला-बदली की जाती है। 20 की तुलना 70 से की जाती है, फिर 20 और 70 की अदला-बदली की जाती है। 20 की तुलना 60 से की जाती है, फिर 20 और 60 की अदला-बदली की जाती है। 20 की तुलना 50 से की जाती है, फिर 20 और 50 की अदला-बदली की जाती है। 20 की तुलना 40 से की जाती है, फिर 20 और 40 की अदला-बदली की जाती है। 20 की तुलना 30 से की जाती है, फिर 20 और 30 की अदला-बदली की जाती है। एक आंदोलन एक ऑपरेशन है। छह तुलना छह ऑपरेशन हैं। छह स्वैप छह ऑपरेशन हैं। यह खंड तेरह संचालन प्रदान करता है। अब तक कुल उनतालीस ऑपरेशन हो चुके हैं (36 + 13 = 49)। परिणाम इस प्रकार है:

20 30 40 50 60 70 80 | 10

सूचकांक सात में, 10 की गति होती है। 10 की तुलना 80 से की जाती है, फिर 10 और 80 की अदला-बदली की जाती है। 10 की तुलना 70 से की जाती है, फिर 10 और 70 की अदला-बदली की जाती है। 10 की तुलना 60 से की जाती है, फिर 10 और 60 की अदला-बदली की जाती है। 10 की तुलना 50 से की जाती है, फिर 10 और 50 की अदला-बदली की जाती है। 10 की तुलना 30 से की जाती है, फिर 10 और 40 की अदला-बदली की जाती है। 10 की तुलना 30 से की जाती है, फिर 10 और 30 की अदला-बदली की जाती है। 10 की तुलना 20 से की जाती है, फिर 10 और 20 की अदला-बदली की जाती है। एक आंदोलन एक ऑपरेशन है। सात तुलना सात ऑपरेशन हैं। सात स्वैप सात ऑपरेशन हैं। यह खंड पंद्रह संचालन प्रदान करता है। अब तक कुल चौंसठ ऑपरेशन हो चुके हैं (49 + 15 = 64)। परिणाम इस प्रकार है:

10 20 30 40 50 60 70 80 10 |

काम हो गया! 64 ऑपरेशन शामिल थे।

64 = 8 x 8 = 8 ^दो

सम्मिलन क्रमबद्ध करने के लिए समय जटिलता

यदि सम्मिलन सॉर्ट के साथ सॉर्ट करने के लिए n तत्व हैं, तो संभावित संचालन की अधिकतम संख्या n2 होगी, जैसा कि पहले दिखाया गया था। सम्मिलन क्रमबद्ध समय जटिलता है:

पर ^दो )

यह बिग-ओ नोटेशन का उपयोग करता है। बिग-ओ नोटेशन अपरकेस में ओ से शुरू होता है, उसके बाद कोष्ठक। कोष्ठक के अंदर संचालन की अधिकतम संभव संख्या के लिए अभिव्यक्ति है।

C . में कोडिंग

स्कैन की शुरुआत में, पहला तत्व अपनी स्थिति नहीं बदल सकता है। कार्यक्रम अनिवार्य रूप से निम्नलिखित है:

इंसर्शनसॉर्ट () फ़ंक्शन परिभाषा वर्णित एल्गोरिदम का उपयोग करती है। जबकि-लूप के लिए शर्तों पर ध्यान दें। इस कार्यक्रम के लिए एक उपयुक्त सी मुख्य कार्य है:

निष्कर्ष

सम्मिलन सॉर्ट के लिए समय जटिलता इस प्रकार दी गई है:

पर ^दो )

पाठक ने शायद बदतर-मामले की समय जटिलता, औसत-केस समय जटिलता और सर्वोत्तम-केस समय जटिलता के बारे में सुना होगा। इंसर्शन सॉर्ट टाइम कॉम्प्लेक्सिटी के इन बदलावों पर हमारी वेबसाइट के अगले लेख में चर्चा की गई है।