Sorting MCQ Quiz in हिन्दी - Objective Question with Answer for Sorting - मुफ्त [PDF] डाउनलोड करें

मर्ज सॉर्ट​ 

यह डिवाइड और कान्क्वर के दृष्टिकोण पर आधारित है।

मर्ज सॉर्ट के लिए पुनरावर्ती संबंध निम्न बन जाएगा:

T(n) = 2T (n/2) + Θ (n)

मास्टर प्रमेय का उपयोग करके

T (n) = n × log₂n

इस प्रकार, मर्ज सॉर्ट की काल जटिलता θ(nlogn) है।

बाइनरी सर्च​

सर्च अंतराल को बार-बार आधे में विभाजित करके क्रमबद्ध सरणी खोजें।

बाइनरी सर्च के लिए पुनरावर्ती T(n) = T(n/2) + θ(1)

मास्टर प्रमेय का उपयोग करके

T (n) = log₂n

इनपुट सूची के केवल आधे हिस्से पर विचार करें और दूसरे आधे को हटा दें। इसलिए काल जटिलता O(log n) है।

प्रमुख बिंदु

• क्विकसॉर्ट एक डिवाइड-एंड- कॉनकॉर एल्गोरिथम है जिसमें पिवट तत्व चुना जाता है, और इस पिवट तत्व ने दी गई समस्या को दो छोटे सेटों में कम कर दिया है।
• त्वरित सॉर्ट सरणियों को छाँटने के लिए उपयोगी है।
• अदक्ष कार्यान्वयन त्वरित सॉर्ट एक स्थिर प्रकार नहीं है, जिसका अर्थ है कि समान प्रकार की वस्तुओं का सापेक्ष क्रम संरक्षित नहीं है।
• त्वरित सॉर्ट की समग्र समय जटिलता O(nLogn) है। सबसे खराब स्थिति में, यह O(n²) तुलना करता है, हालांकि यह व्यवहार दुर्लभ है।
• त्वरित सॉर्ट की अंतरिक्ष जटिलता O(nLogn) है। यह एक इन-प्लेस सॉर्ट है (यानी इसे किसी अतिरिक्त संग्रहण की आवश्यकता नहीं है)।

इसलिए सही उत्तर डिवाइड-एंड-कॉन्कर रणनीति है।

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

सही उत्तर अनसुपरवाइज्ड लर्निंग है।

Key Points 

1. पर्यवेक्षित शिक्षण:

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

2. बिना पर्यवेक्षण के सीखना:

• बिना पर्यवेक्षित शिक्षण में, एल्गोरिदम को बिना किसी स्पष्ट निर्देश के डेटा दिया जाता है कि इसके साथ क्या करना है।
• एल्गोरिदम स्वयं डेटा के भीतर पैटर्न, संबंध या संरचना ढूंढने का प्रयास करता है।
• क्लस्टरिंग एल्गोरिदम, जैसे के-मीन्स, बिना पर्यवेक्षित शिक्षण के अंतर्गत आते हैं क्योंकि वे लेबल किए गए आउटपुट जानकारी का उपयोग किए बिना समान डेटा बिंदुओं को एक साथ समूहित करते हैं।

3. अर्ध-पर्यवेक्षित शिक्षण:

• अर्ध-पर्यवेक्षित शिक्षण पर्यवेक्षित और गैर-पर्यवेक्षित शिक्षण का एक संयोजन है।
• इसमें एक डेटासेट शामिल होता है जिसमें लेबल किए गए और बिना लेबल वाले दोनों उदाहरण होते हैं।
• एल्गोरिदम को लेबल किए गए डेटा पर प्रशिक्षित किया जाता है, और फिर यह लेबल किए गए डेटा से सीखे गए पैटर्न का लाभ उठाकर गैर-लेबल वाले डेटा पर भविष्यवाणियां करने का प्रयास करता है।

4. सुदृढीकरण सीखना:

• सुदृढीकरण सीखने में एक एजेंट पर्यावरण के साथ बातचीत करता है और पुरस्कार या दंड के रूप में प्रतिक्रिया प्राप्त करके निर्णय लेना सीखता है।
• एजेंट ऐसे कार्य करना सीखता है जो समय के साथ संचयी इनाम को अधिकतम करते हैं।
• पर्यवेक्षित शिक्षण के विपरीत, जहां एल्गोरिदम को स्पष्ट लेबल वाले उदाहरण प्रदान किए जाते हैं, सुदृढीकरण सीखने में, एल्गोरिदम परीक्षण और त्रुटि से सीखता है।

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

सही उत्तर n - 1 है।

Key Points

• चयन क्रम एक इन-प्लेस तुलना क्रम एल्गोरिथम है जो इनपुट सूची को दो भागों में विभाजित करता है: आइटमों की एक क्रमबद्ध उपसूची जो बाएँ से दाएँ बनती है और शुरू में खाली होती है, और शेष असंक्रमित मदों की एक उपसूची जो सूची के बाकी हिस्से पर कब्जा कर लेती है।
  • एल्गोरिथम असंक्रमित उपसूची में सबसे छोटे (या सबसे बड़े, सॉर्टिंग क्रम के आधार पर) तत्व को ढूंढकर आगे बढ़ता है, इसे सबसे बाएँ असंक्रमित तत्व के साथ बदलता (स्वैप करता) है (इसे क्रमबद्ध क्रम में रखता है), और उपसूची सीमाओं को एक तत्व दाईं ओर ले जाता है।
  • n तत्वों की सूची को क्रमबद्ध करने के लिए, चयन क्रम सूची के माध्यम से n - 1 पास करता है। ऐसा इसलिए है क्योंकि, प्रत्येक पास में, यह एक तत्व को अपनी सही स्थिति में रखता है, और n - 1 पास के बाद, शेष तत्व पहले से ही अपनी सही स्थिति में है।
  • प्रत्येक पास के दौरान, एल्गोरिथम असंक्रमित उपसूची से सबसे छोटे (या सबसे बड़े) तत्व का चयन करता है और इसे सबसे बाएँ असंक्रमित तत्व के साथ स्वैप करता है, प्रभावी रूप से क्रमबद्ध उपसूची को एक तत्व से बढ़ाता है।

Additional Information

• चयन क्रम में प्रविष्‍ट पाशों के कारण O(n^2) की समय जटिलता होती है: एक पास के लिए और दूसरा न्यूनतम तत्व खोजने के लिए।
• हालाँकि यह बड़ी सूचियों के लिए सबसे कुशल क्रमबद्ध एल्गोरिथम नहीं है, यह छोटी सूचियों पर अच्छा प्रदर्शन करता है और इसे समझने और लागू करने में आसान होने का लाभ है।
• चयन क्रम एक स्थिर क्रम नहीं है, जिसका अर्थ है कि यह समान तत्वों के सापेक्ष क्रम को संरक्षित नहीं करता है।
• यह एक इन-प्लेस क्रमबद्ध एल्गोरिथम है, जिसके लिए केवल अतिरिक्त मेमोरी स्थान की एक निरंतर मात्रा की आवश्यकता होती है।

सही उत्तर अनसुपरवाइज्ड लर्निंग है।

Key Points 

1. पर्यवेक्षित शिक्षण:

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

2. बिना पर्यवेक्षण के सीखना:

• बिना पर्यवेक्षित शिक्षण में, एल्गोरिदम को बिना किसी स्पष्ट निर्देश के डेटा दिया जाता है कि इसके साथ क्या करना है।
• एल्गोरिदम स्वयं डेटा के भीतर पैटर्न, संबंध या संरचना ढूंढने का प्रयास करता है।
• क्लस्टरिंग एल्गोरिदम, जैसे के-मीन्स, बिना पर्यवेक्षित शिक्षण के अंतर्गत आते हैं क्योंकि वे लेबल किए गए आउटपुट जानकारी का उपयोग किए बिना समान डेटा बिंदुओं को एक साथ समूहित करते हैं।

3. अर्ध-पर्यवेक्षित शिक्षण:

• अर्ध-पर्यवेक्षित शिक्षण पर्यवेक्षित और गैर-पर्यवेक्षित शिक्षण का एक संयोजन है।
• इसमें एक डेटासेट शामिल होता है जिसमें लेबल किए गए और बिना लेबल वाले दोनों उदाहरण होते हैं।
• एल्गोरिदम को लेबल किए गए डेटा पर प्रशिक्षित किया जाता है, और फिर यह लेबल किए गए डेटा से सीखे गए पैटर्न का लाभ उठाकर गैर-लेबल वाले डेटा पर भविष्यवाणियां करने का प्रयास करता है।

4. सुदृढीकरण सीखना:

• सुदृढीकरण सीखने में एक एजेंट पर्यावरण के साथ बातचीत करता है और पुरस्कार या दंड के रूप में प्रतिक्रिया प्राप्त करके निर्णय लेना सीखता है।
• एजेंट ऐसे कार्य करना सीखता है जो समय के साथ संचयी इनाम को अधिकतम करते हैं।
• पर्यवेक्षित शिक्षण के विपरीत, जहां एल्गोरिदम को स्पष्ट लेबल वाले उदाहरण प्रदान किए जाते हैं, सुदृढीकरण सीखने में, एल्गोरिदम परीक्षण और त्रुटि से सीखता है।

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

संकल्पना:

मैक्स-हीप: मैक्स-हीप में, रूट नोड हमेशा ट्री के अन्य नोड से बड़ा या बराबर होता है।

व्याख्या:

A = <4, 1, 3, 2, 16, 9, 10, 14, 8, 7> है।

चरण 1

अब, चूंकि 2 1 से बड़ा है, इसलिए नोड की पुनर्व्यवस्था की आवश्यकता है।

चरण 2:

फिर से 16 को 2 के साथ एक्सचेंज करें। मैक्स-हीप के गुण के अनुसार शेष नोड इन्सर्ट करें।

चरण 3:

चरण 4:

चरण 5:

इस तरह से सभी नोड इन्सर्ट करने के बाद, अंतिम मैक्स - हीप है:

बबल सॉर्ट बार-बार वर्गीकृत करने के लिए सूची के माध्यम से जाता है, आसन्न वस्तुओं की प्रत्येक जोड़ी की तुलना करता है और यदि वे गलत क्रम में हैं तो उन्हें बदल देता है। सूची के माध्यम से पास तब तक दोहराया जाता है जब तक कि कोई अदला बदली की आवश्यकता न हो, जो इंगित करता है कि सूची को क्रमबद्ध किया गया है।

सरणी घटक: 8, 22, 7, 9, 31, 5, 13

1^st पास= 8, 7, 9, 22, 5, 13, 31

4 अदला बदली (स्वैप्स)

2^nd पास= 7, 8, 9, 5, 13, 22, 31

3 अदला बदली (स्वैप्स)

3^rd पास= 7, 8, 5, 9, 13, 22, 31

1 अदला बदली (स्वैप्स)

4^th पास= 7, 5, 8, 9, 13, 22, 31

1 अदला बदली (स्वैप्स)

5^th पास= 5, 7, 8, 9, 13, 22, 31

1 अदला बदली (स्वैप्स)

चूँकि सरणी को पाँचवे पास के बाद वर्गीकृत किया जाता है

∴ आगे कोई अदला-बदली संभव नहीं है

अदला-बदली की कुल संख्या = 4 + 3 + 1 + 1 + 1 = 10 

सही उत्तर विकल्प 3 है।

Key Points

• क्विकसाॅर्ट एक कुशल वर्गीकरण एल्गोरिथ्म है जिसे विभाजन-विनिमय सॉर्ट के रूप में भी जाना जाता है।
• क्विकसाॅर्ट एक तुलनात्मक साॅर्ट है, जिसका अर्थ है कि यह किसी भी प्रकार की वस्तुओं को सॉर्ट कर सकता है जिसके लिए "less-than" संबंध परिभाषित किया जाता है।
• क्विकसाॅर्ट एक डिवाइड एण्ड कान्क्वर एल्गोरिथ्म है जिसमें पिवट घटक को चुना जाता है, और यह पिवट घटक दी गई समस्या को दो छोटे सेट में कम कर देता है।
• कुशल कार्यान्वयन में, यह एक स्थिर साॅर्ट नहीं है, जिसका अर्थ है कि समान साॅर्ट वस्तुओं का सापेक्ष क्रम संरक्षित नहीं होता है।
• क्विकसाॅर्ट एक सरणी पर  in-place को संचालित कर सकता है, जिससे छँटाई करने के लिए छोटी अतिरिक्त मात्रा में मेमोरी की आवश्यकता होती है।

Additional Information

क्विकसाॅर्ट :

क्विकसाॅर्ट में, निकृष्ठ प्रकरण में Θ (n2) समय लगता है। क्विकसाॅर्ट का निकृष्ठ प्रकरण तब होता है जब पहला या आखिरी घटक पिवट घटक के रूप में चुना जाता है।

आरेख

\(\mathop \sum \limits_{{\rm{p}} = 1}^{{\rm{N}} - 1} {\rm{p}} = 1 + 2 + 3 + \ldots . + {\rm{N}} - 1 = {\rm{\;}}\frac{{{\rm{N}}\left( {{\rm{N}} - 1} \right)}}{2} - 1\)

यह Θ (n2) समय जटिलता देता है।

क्विकसाॅर्ट एल्गोरिथ्म के लिए पुनरावृत्ति संबंध निम्न होगा

T (n) = T (n-1) + Θ (n)

यह निकृष्ठ प्रकरण समय जटिलता  Θ (n2) के रुप में देता है।

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

इसलिए विकल्प 4 सही उत्तर है।

इंसर्शन सॉर्ट​:

इंसर्शन सॉर्ट में, सर्वश्रेष्ठ मामले में Θ (n) समय लगता है, इंसर्शन सॉर्ट का सर्वश्रेष्ठ मामला तब होता है जब घटकों को आरोही क्रम में सॉर्टेड किया जाता है। उस स्थिति में, तुलनाओं की संख्या n - 1 = 8 - 1 = 7 होगी

उपरोक्त सरणी को आरोही क्रम में क्रमबद्ध करने के लिए यह तुलना की न्यूनतम संख्या (सरणी घटकों के बीच) है:

आवश्यक स्वैप की संख्या शून्य है।

Additional Information

इंसर्शन सॉर्ट में, सबसे खराब मामले में Θ (n2) समय लगता है, इंसर्शन सॉर्ट का सबसे खराब मामला तब होता है जब घटकों को विपरीत क्रम में सॉर्टेड किया जाता है। उस स्थिति में, तुलनाओं की संख्या निम्न होगीः

\(\mathop \sum \limits_{{\rm{p}} = 1}^{{\rm{N}} - 1} {\rm{p}} = 1 + 2 + 3 + \ldots . + {\rm{N}} - 1 = {\rm{\;}}\frac{{{\rm{N}}\left( {{\rm{N}} - 1} \right)}}{2} - 1\)

यह Θ (n2) समय जटिलता देगा।

पूर्ण बाइनरी ट्री पर विचार करें जहाँ रूट के बाएँ और दाएँ उपट्री नीचे दिए गए अधिकतम-हीप हैं

ट्री को हीप में बदलने के लिए जो रूट पर MAX-HEAPIFY को कॉल करना संभव होता है। MAX- HEAPIFY ऑपरेशन में ट्री की ऊंचाई के रूप में समय लगता है। यानी अगर हमारे पास ट्री में n तत्व हैं तो log(n) ट्री की ऊंचाई है।

चरण 1: स्वैप 10 और 40

चरण 2: स्वैप 10 और 25

उपरोक्त ट्री एक MAX-HEAP है

इसे अधिकतम हीप में बदलने के लिए केवल 2 स्वैप और 2  होती है जो कि ट्री की ऊंचाई के अलावा और कुछ नहीं है। तो, ट्री को हीप में बदलने के लिए log(n)  समय की आवश्यकता होती है।

Key Points

• मिन-हीप एक पूर्ण बाइनरी ट्री डेटा संरचना है जिसमें पैरेंट नोड का मान उसके चिल्ड्रेन नोड से छोटा होता है।

• मिन-हीप में, लीफ नोड या अंतिम स्तर में सरणी के अधिकतम मान होते हैं।

व्याख्या:

यदि हम पाशविक बल तकनीक का उपयोग करते हैं, तो बाइनरी मिन-हीप में सबसे बड़ा तत्व खोजने में O(n) समय लगेगा।

यदि हम मिन-हीप के गुण का उपयोग करते हैं:

मिन-हीप गुण के लिए आवश्यक है कि पैरेंट नोड उसके चाइल्ड नोड से कम हो। इसके कारण, हम यह निष्कर्ष निकाल सकते हैं कि एक गैर-लीफ नोड अधिकतम तत्व नहीं हो सकता क्योंकि उसके चाइल्ड नोड का मान कम होता है।

इसलिए हम अपने खोज स्थान को केवल लीफ नोड्स तक सीमित कर सकते हैं। n तत्वों वाले मिन-हीप में, ceil(n/2) लीफ नोड्स होते हैं। समय और स्थान की जटिलता O(n) बनी रहती है क्योंकि 1/2 का एक स्थिर कारक स्पर्शोन्मुख जटिलता को प्रभावित नहीं करता है।

Additional Information

मिन-हीप में न्यूनतम तत्व θ(1) लेता है।

सही उत्तर विकल्प 3 है

Key Points

• बबल सॉर्ट एल्गोरिथ्म आसन्न तत्वों को बार-बार स्वैप करके काम करता है जो तब तक क्रम में नहीं होता, जब तक कि वस्तुओं की पूरी सूची क्रम में न हो।
• यदि सॉर्टिंग एक ही पुनरावृत्ति में पूरी हो जाती है, तो यह पता लगाया जा सकता है कि इनपुट पहले से ही सॉर्टेड है।

Additional Information

• जब इनपुट के तत्वों को पहले से ही सॉर्टेड किया जाता है, तो बबल सॉर्ट सर्वश्रेष्ठ समय जटिलता O(n) देता है।
• बबल सॉर्ट आमतौर पर इसके पुनरावृत्त व्यवहार के कारण धीमा होता है।

सही उत्तर विकल्प 3 है।

संकल्पना:

अधिकतम-हीप:

अधिकतम-हीप एक पूर्ण बाइनरी ट्री है जिसमें प्रत्येक आंतरिक नोड का मान उस नोड के चिल्ड्रन के मूल्यों से अधिक या उसके बराबर होता है। एक हीप के तत्वों को एक सरणी में मैप करना नगण्य है: यदि एक नोड को एक इंडेक्स k संग्रहीत किया जाता है, तो उसके बाएं चिल्ड्रन को इंडेक्स 2k+1 और उसके दाहिने चिल्ड्रन को इंडेक्स 2k+2 पर संग्रहीत किया जाता है।

तत्वों की दी गई सरणी निम्न हैं,

<70, 23, 60, 19, 13, 16, 1, 4, 8, 12, 7, 10, 85> हीप ट्री निम्न बन जाता है,

एक बाइनरी ट्री को हीप डेटा संरचना में बदलने की प्रक्रिया को 'हेपिफाई' के रूप में जाना जाता है। बाइनरी ट्री एक ट्री डेटा संरचना है जिसमें अधिकतम दो चाइल्ड नोड होते हैं। यदि किसी नोड के चिल्ड्रन के नोड्स 'हेपिफाइड' हैं, तो उस नोड पर केवल 'हेपिफाई' प्रक्रिया लागू की जा सकती है। हीप हमेशा एक पूर्ण बाइनरी ट्री होना चाहिए। हेपिफाई विधि एक सरणी के तत्वों को पुनर्व्यवस्थित करती है जहाँ ith तत्व का बायाँ और दायाँ उप-वृक्ष हीप गुण का पालन करता है। हेपिफाई स्तर दर स्तर पत्तियों से जड़ नोड्स तक कर सकता है।

तो कुल 3 स्वैप की आवश्यकता है।

अतः सही उत्तर 3 है।