Searching, Sorting and Hashing MCQ Quiz in हिन्दी - Objective Question with Answer for Searching, Sorting and Hashing - मुफ्त [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

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

Additional Information

• सरणियाँ:
  • सरणियाँ एक सूचकांक का उपयोग करके अवयवों तक नियत समय पहुंच प्रदान करते हैं।
  • उनका एक निश्चित आकार होता है, जिससे यदि सरणी उसमें मौजूद अवयवों की वास्तविक संख्या से बड़ी हो तो मेमोरी बेकार हो सकती है।
  • संचालन को तेज़ करने के लिए किसी अतिरिक्त मेमोरी का उपयोग नहीं किया जाता है, और एक्सेस समय पहले से ही कुशल होता है।
• लिंक्ड सूचियाँ:
  • लिंक्ड सूचियाँ गतिशील मेमोरी आवंटन प्रदान करती हैं, जिससे अवयवों को कुशल सम्मिलन और हटाने की अनुमति मिलती है।
  • हालाँकि, किसी विशिष्ट सूचकांक पर किसी अवयव तक पहुँचने में रैखिक समय लगता है, क्योंकि आपको शुरुआत से ही सूची को पार करना होगा।
  • लिंक्ड सूचियाँ संचालन को गति देने के लिए अतिरिक्त मेमोरी का उपयोग नहीं करती हैं।
• स्टैक:
  • स्टैक लास्ट-इन-फर्स्ट-आउट (LIFO) सिद्धांत का पालन करते हैं और एक छोर पर अवयवों को कुशल सम्मिलन और हटाने की अनुमति देते हैं।
  • इन्हें आम तौर पर सरणियों या लिंक्ड सूचियों का उपयोग करके कार्यान्वित किया जाता है।
  • स्टैक संचालन को गति देने के लिए अतिरिक्त मेमोरी का उपयोग नहीं करते हैं; उनकी दक्षता LIFO संरचना की प्रकृति से आती है।

सही उत्तर रैखिक जांच है। 

Key Points

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

Additional Information

• द्विघात जांच:
  • रैखिक जांच के समान, लेकिन एक समय में एक स्थान को स्थानांतरित करने के बजाय, द्विघात जांच जांच के लिए अगली स्थिति निर्धारित करने के लिए एक द्विघात फलन का उपयोग करती है।
  • यदि हैश सूचकांक पर स्थान पर कब्जा कर लिया गया है, तो यह क्रमिक वर्गों द्वारा बढ़ाए गए पदों पर स्थान की जांच करता है।
  • द्विघात जांच, रैखिक जांच की तुलना में समूहीकरण को कम करने में मदद करती है।
• पृथक श्रृंखला:
  • संघट्टित अवयवों को हैश तालिका में अगले उपलब्ध स्थान में रखने के बजाय, अलग श्रृंखला में हैश तालिका में प्रत्येक स्थान पर एक लिंक की गई सूची बनाए रखना शामिल है।
  • जब कोई संघट्ट होता है, तो संघट्टित अवयव उस स्थान पर लिंक की गई सूची में जुड़ जाते हैं।
  • संघट्ट को संभालने के लिए प्रत्येक स्थान में एक अलग डेटा संरचना (जैसे लिंक की गई सूची या वृक्ष) होती है।
• द्वि-हैशिंग:
  • द्वि-हैशिंग में, जांच प्रयासों के बीच चरण आकार निर्धारित करने के लिए एक द्वितीयक हैश फलन का उपयोग किया जाता है।
  • यदि कोई संघट्ट होता है, तो एल्गोरिदम जांच के लिए एक नए सूचकांक की गणना करने के लिए द्वितीयक हैश फलन का उपयोग करता है।
  • यह समूहन से बचने में मदद करता है और खाली स्थान ढूंढने का अधिक व्यवस्थित तरीका प्रदान करता है।

सही विकल्प हैशिंग के द्वारा सर्च है।

संकल्पना:

रैखिक सर्च में, दी गई सूची के प्रत्येक घटक की तुलना किसी भी घटक को छोड़े बिना दी गई कुंजी(की) के साथ एक-एक करके की जाती है।

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

उदाहरण के लिए, लंबाई 5 की एक सूची पर विचार करें और मुख्य घटक इस सूची के अंत में मौजूद है। प्रमुख घटक को खोजने के लिए आवश्यक तुलनाओं की संख्या = सूची का आकार अर्थात् 5

यदि हम उसी सूची का आकार बढ़ाते हैं (मान लीजिए 15) और मुख्य घटक इस सूची के अंत में मौजूद है। प्रमुख घटक को खोजने के लिए आवश्यक तुलनाओं की संख्या = सूची का आकार अर्थात् 15

बाइनरी सर्च में, खोजी जाने वाली कुंजी(की) की तुलना वर्गीकृत सूची के बीच के घटक से की जाती है, इसके परिणामस्वरूप तीन में से कोई भी संभावना हो सकती है:

i) यदि मध्य स्थिति का घटक कुंजी(की) से मेल खाता है तो खोज सफल होती है।

ii) यदि मध्य स्थिति का घटक कुंजी(की) से बड़ा है तो मुख्य घटक सूची के बाएं भाग में मौजूद हो सकता है।

iii) यदि मध्य स्थान पर स्थित घटक कुंजी(की) से छोटा है, तो कुंजी घटक सूची के दाहिने हिस्से में मौजूद हो सकता है।

यह प्रक्रिया तब तक जारी रहती है जब तक कि घटक नहीं मिल जाता या सूची पूरी तरह से ट्रेवर्स्ड नहीं हो जाती।

इस प्रकार जैसे-जैसे सूची का आकार बढ़ता है, सूची को खोजने में लगने वाला समय बढ़ता जाता है। लेकिन यह रैखिक सर्च के लिए आवश्यक समय जितना बड़ा नहीं होगा।

हैश-आधारित सर्चिंग के लिए कुंजी(की) की स्थिति का पता लगाने के लिए केवल एक कुंजी(की) तुलना की आवश्यकता होती है, बशर्ते कि प्रत्येक घटक हैश फलन द्वारा तय की गई अपनी निर्दिष्ट स्थिति में मौजूद हो।

उदाहरण के लिए, लंबाई 5 और हैश फलन की सूची पर विचार करें:

फलन: h(element) = element % size(list)

हैशिंग फलन एक गणितीय फलन है जो स्थिर समय में हैश फलन को प्रदान किए गए प्रत्येक अद्वितीय मान के लिए अद्वितीय परिणाम उत्पन्न करता है।

उदाहरण के लिए: लंबाई 5 की एक सूची पर विचार करें और यदि हम कुंजी(की) = 12 की खोज करना चाहते हैं, तो हैश फलन द्वारा रिटर्न किया गया सूचकांक h(12) = 12% 5 = 2 है और सूचकांक पर कुंजी(की) खोजने के लिए केवल एक कुंजी(की) तुलना की आवश्यकता होती है। 

उसी तरह सूची का आकार बढ़ाना (15 मान लें) और यदि हम कुंजी(की) = 12 की खोज करना चाहते हैं, तो हैश फलन द्वारा रिटर्न किया गया सूचकांक h(12) = 12% 5 = 12 है और सूचकांक पर कुंजी(की) खोजने के लिए केवल एक कुंजी तुलना की आवश्यकता है।

इस प्रकार यह सूची की लंबाई से स्वतंत्र होता है।

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

Key Points 

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

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

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

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

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

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

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

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

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

चूंकि हम यादृच्छिक प्रोबिंग का उपयोग कर रहे हैं:

इन्सर्ट 15:

(15)%7 = 1

इन्सर्ट 11:

(11)%7 = 4

इन्सर्ट 25:

(25)%7 = 4 / संघट्‍टन:

i = 4

 i = (i + 5) % 7    / यादृच्छिक फ़ंक्शन का उपयोग करना

i = (4 + 5)%7 = 2

अत: 25 की स्थिति 2nd है 

अवधारणा:

• एक लीनियर सर्च (रैखिक खोज) या ​(सिक्वेंशियल सर्च) अनुक्रमिक खोज एक ऐरे या लिंक्ड सूची या किसी डेटा संरचना के भीतर एक घटक खोजने के लिए एक विधि है।
• यह अनुक्रमिक रूप से सूची के प्रत्येक घटक की तब तक जांच करता है जब तक कि कोई मैच नहीं मिलता है या पूरी सूची सर्च कर ली गई है।

स्पष्टीकरण:

int A[ ] = {2, 1, 4, 5 , 6, 7}

ऐरे का नाम: A

सर्च: 2

पहली तुलना में, 2 पाया जाता है

सर्वोत्तम-केस समय जटिलता O(1) है

संकल्पना:

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

व्याख्या:

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) समय जटिलता देगा।

बाइनरी सर्च एल्गोरिथ्म:

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

चरण 1:

• यह सरणी के मध्य तत्व को ढूंढता है और खोजे जाने वाले तत्व के साथ तत्व की तुलना करता है, यदि यह मेल खाता है तो सत्य प्राप्त होता है।

चरण 2:

• यदि नहीं, तो सरणी को दो हिस्सों में विभाजित कीजिये जिसमें खोज के लिए तत्व मध्य तत्व से कम है, तो खोज बाएं भाग में होती है अन्यथा दाएं आधे में खोजें।

चरण 3:

इस प्रक्रिया को तब तक दोहराएं जब तक आपको तत्व न मिल जाए।

व्याख्या:

सबसे खराब स्थिति के लिए 52

सबसे खराब स्थिति: नीचे दिए गए सरणी में 50 खोजें

\({\rm{midde\;index}} = \frac{{0 + 9}}{2} = 4\therefore {\rm{a}}\left[ 4 \right] = 35\)

50 > 32

\({\rm{midde\;index}} = \frac{{5 + 9}}{2} = 7\;\therefore {\rm{a}}\left[ 7 \right] = 63\)

50 < 63

\({\rm{midde\;index}} = \frac{{5 + 6}}{2} = 8\;\therefore {\rm{a}}\left[ 5 \right] = 50\)

मिल गया 

T(n) = O(log n)

इसके अलावा, औसत स्थिति के लिए:

T(n) = O(log n)

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

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

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

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

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

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