प्रोग्रामिंग, डेटा संरचनाएँ एवं एल्गोरिथ्म

GATE आँकड़ा विज्ञान व कृत्रिम बुद्धिमत्ता (DA) पेपर का खंड 4। डेटा वैज्ञानिक जो भी मॉडल प्रशिक्षित करता है वह ऐसे कोड पर टिका होता है जिसे सही ढंग से चलना और समय पर पूरा होना ही चाहिए, और यह खंड ठीक उसी नींव की जाँच करता है: Python में प्रोग्रामिंग, वे मुट्ठी-भर डेटा संरचनाएँ — स्टैक, क्यू, लिंक्ड लिस्ट, ट्री, हैश टेबल — जिन पर इस पेपर की हर बड़ी संरचना बनी है, खोज व क्रमबद्धता (sorting) एल्गोरिथ्म जहाँ दक्षता पर पहली बार वास्तव में तर्क किया जाता है न कि मान लिया जाता है, वह भाग-और-जीतो (divide-and-conquer) तकनीक जो mergesort व quicksort दोनों लागू करते हैं, तथा ग्राफ़ सिद्धांत उन ट्रैवर्सल व न्यूनतम-पथ एल्गोरिथ्म सहित जो संबंधों के किसी जाल को कंप्यूटर द्वारा खोजने योग्य किसी चीज़ में बदल देते हैं।

1. Python, तथा पहली डेटा संरचनाएँ: स्टैक व क्यू

पाठ्यक्रम विशेष रूप से Python नाम लेता है, क्योंकि डेटा-विज्ञान कार्यक्रम को किसी भाषा के पूर्ण फीचर-सेट से कम, उसकी मानक लाइब्रेरी व परितंत्र (ecosystem) द्वारा तैयार-तैयार दी गई संरचनाओं से सरोकार होता है। स्टैक Last-In-First-Out (LIFO) है: push शीर्ष पर जोड़ता है, pop शीर्ष से हटाता है, और दोनों O(1) हैं। क्यू First-In-First-Out (FIFO) है: enqueue पिछले सिरे पर जोड़ता है, dequeue अगले सिरे से हटाता है, और दोनों भी O(1) होने चाहिए — बशर्ते अंतर्निहित संरचना वास्तव में अगले सिरे से हटाना सस्ते में समर्थित करे।

⚠️ Python का list.pop(0) O(1) नहीं है
Python की list एक गतिशील ऐरे है, और उसका पहला अवयव हटाने का अर्थ है शेष हर अवयव को एक स्थान बाईं ओर खिसकाना — यह O(n) है, O(1) नहीं। plain list को pop(0) के ज़रिए क्यू की तरह उपयोग करना चुपचाप एक O(1)-प्रति-संक्रिया संरचना को O(n)-प्रति-संक्रिया में बदल देता है; मानक लाइब्रेरी का अपना deque (द्वि-अंत क्यू) दोनों सिरों पर O(1) append व pop हेतु बना है, और यही वह संरचना है जिसका यह खंड का क्यू वास्तव में वर्णन करता है।
  • स्टैक का क्लासिक उपयोग है हाथ से recursion को खोलना — हर फ़ंक्शन-कॉल फ़्रेम स्वयं एक कॉल-स्टैक पर push होता है, यही कारण है कि गहरी असीमित recursion उसे overflow कर देती है।
  • क्यू का क्लासिक उपयोग है चौड़ाई-प्रथम (breadth-first) ट्रैवर्सल, जहाँ 'अगले स्तर से पहले इसी स्तर का सब कुछ संसाधित करो' ठीक वही है जो FIFO क्रम मुफ़्त में देता है।

2. लिंक्ड लिस्ट, ट्री एवं हैश टेबल

लिंक्ड लिस्ट हर अवयव को अपने ही नोड में रखती है जो अगले की ओर एक पॉइंटर वहन करता है, अतः किसी ज्ञात स्थिति पर सम्मिलन या विलोपन वहाँ पहुँचने के बाद O(1) है — कोई खिसकाव नहीं — पर उस स्थिति तक, या इंडेक्स से किसी भी स्थिति तक पहुँचना O(n) खर्च करता है क्योंकि कोई रैंडम एक्सेस नहीं, ऐरे के O(1) इंडेक्सिंग के विपरीत। ट्री किसी नोड को एक से अधिक 'अगला' रखने देकर लिंक्ड लिस्ट को सामान्यीकृत करता है: बाइनरी ट्री में हर नोड के अधिकतम दो संतान होते हैं, और उसका आकार तय करता है कि उस पर संक्रिया O(log n) (संतुलित ट्री) है या O(n) तक बिगड़ जाती है (ट्री जो एक सीधी शृंखला बन चुका है)।

हैश टेबल किसी कुंजी को हैश फ़ंक्शन के ज़रिए ऐरे इंडेक्स से मैप करती है, जो औसत-स्थिति में O(1) सम्मिलन, खोज व विलोपन देता है — इस सूची में किसी संख्यात्मक स्थिति के बजाय किसी मनमानी कुंजी से लगभग 'मुफ़्त' रैंडम एक्सेस के सबसे निकट। दो कुंजियों का एक ही इंडेक्स पर हैश होना collision है, जिसे chaining (हर स्लॉट वहाँ पहुँचीं कुंजियों की एक छोटी लिस्ट रखता है) या open addressing (अगले खाली स्लॉट तक आगे जाँच) से सुलझाया जाता है; किसी भी तरह, जब collision ढेर हो जाएँ तो worst-case खोज O(n) है, यही कारण है कि हल-योजना से अधिक अच्छा हैश फ़ंक्शन व नियंत्रित load factor मायने रखते हैं।

संरचना अनुसार सामान्य समय जटिलता (औसत स्थिति)
संरचनाइंडेक्स/कुंजी से एक्सेसखोजसम्मिलन
ऐरेO(1)O(n)O(n)
लिंक्ड लिस्टO(n)O(n)O(1), ज्ञात नोड पर
संतुलित बाइनरी ट्रीO(log n)O(log n)O(log n)
हैश टेबलO(1) औसतO(1) औसतO(1) औसत

3. खोज एल्गोरिथ्म एवं बुनियादी क्रमबद्धता

Linear search हर अवयव को बारी-बारी जाँचता है, O(n), और डेटा के बारे में कुछ भी मान लेने की ज़रूरत नहीं। Binary search लक्ष्य की मध्य अवयव से तुलना करके खोज-सीमा को बार-बार आधा करता है, O(log n) — पर केवल पहले से क्रमबद्ध डेटा पर; इसे अक्रमबद्ध डेटा पर चलाएँ तो यह ग़लत उत्तर दे सकता है या वास्तव में मौजूद अवयव को चूक सकता है, क्योंकि आधा करने के चरण का पूरा तर्क क्रम पर निर्भर है।

Selection sort बार-बार अक्रमबद्ध शेष भाग का न्यूनतम खोजता है और उसे उसकी जगह पर स्वैप करता है — इनपुट के आरंभिक क्रम से निरपेक्ष सदा ठीक n(n-1)/2 तुलनाएँ, अतः इसकी सर्वश्रेष्ठ व सबसे बुरी स्थिति समान है। Bubble sort बार-बार सटे हुए अक्रमबद्ध जोड़ों को स्वैप करता है, और जो क्रियान्वयन एक पूरे पास में कोई स्वैप न होने पर जल्दी रुक जाता है वह पहले से क्रमबद्ध ऐरे पर O(n) तक पहुँचता है। Insertion sort एक बार में एक अवयव करके क्रमबद्ध प्रीफ़िक्स बनाता है, हर नए अवयव को पहले से क्रमबद्ध अवयवों में उसके सही स्थान पर सम्मिलित करता है: worst case O(n²), पर लगभग-क्रमबद्ध डेटा पर best case O(n), क्योंकि हर नए अवयव को तब लगभग कोई खिसकाव नहीं चाहिए।

🎯 व्यवहार में insertion sort अब भी 'बेहतर' सॉर्ट्स को क्यों हरा देता है
कोई O(n log n) सॉर्ट किसी O(n²) से asymptotically तेज़ तभी होता है जब n इतना बड़ा हो कि स्थिरांक व निम्न-कोटि पद मायने रखना बंद कर दें। छोटी ऐरे पर, या ऐसे डेटा पर जो पहले से लगभग क्रमबद्ध हो (व्यवहार में सामान्य स्थिति, जैसे नए अभिलेखों के एक छोटे बैच को पहले से क्रमबद्ध संग्रह में मिलाना), insertion sort की लगभग-रैखिक best case व कम स्थिरांक-भार वास्तव में जीतते हैं, यही कारण है कि उत्पादन सॉर्ट क्रियान्वयन अक्सर किसी बड़े, asymptotically तेज़ सॉर्ट के भीतर एक छोटी आकार-सीमा से नीचे इसी पर लौट आते हैं।

4. भाग-और-जीतो: mergesort व quicksort

दोनों एल्गोरिथ्म ऐरे को बाँटते हैं, भागों पर recurse करते हैं, और मिलाते हैं — पाठ्यक्रम में नामित भाग-और-जीतो प्रतिरूप — पर वे काम को भिन्न ढंग से बाँटते हैं। Mergesort ऐरे को स्थिति से आधा बाँटता है, हर आधे को recursively क्रमबद्ध करता है, फिर दोनों क्रमबद्ध आधों को O(n) में मिलाता है: बँटवारा तुच्छ है और असली काम मिलाने के चरण में होता है। इसका रनिंग टाइम हर स्थिति में — best, worst व average समान रूप से — Θ(n log n) है, क्योंकि बँटवारा डेटा से निरपेक्ष सदा बराबर होता है, पर मिलाने के चरण हेतु इसे O(n) सहायक स्थान चाहिए और यह stable है (बराबर अवयव अपना सापेक्ष क्रम बनाए रखते हैं)।

Quicksort स्थिति के बजाय मान से बाँटता है: यह एक पिवट चुनता है, ऐरे को इस तरह विभाजित करता है कि हर छोटा अवयव उसके बाईं ओर व हर बड़ा दाईं ओर बैठे (असली काम), फिर दोनों ओर recurse करता है, जो पिवट के सापेक्ष पहले ही सही स्थान पर हैं और उन्हें मिलाने के किसी चरण की ज़रूरत ही नहीं। व्यवहार में in-place व कैश-मैत्रीपूर्ण, इसका औसत Θ(n log n) है — पर इसका worst case Θ(n²) है, जो तब पहुँचता है जब विभाजन हर चरण में अधिकतम असंतुलित हो।

⚠️ पिवट भोलेपन से चुनें तो quicksort का worst case दुर्लभ किनारा-मामला नहीं रहता
पहले (या अंतिम) अवयव को हमेशा पिवट चुनना किसी पहले-से-क्रमबद्ध या उल्टे-क्रमबद्ध ऐरे पर — जो एक बिलकुल साधारण इनपुट है, कोई गढ़ा हुआ adversarial नहीं — हर बार Θ(n²) worst case तक पहुँचा देता है, क्योंकि हर विभाजन शेष सभी n-1 अवयवों को एक ही ओर रख देता है। यही कारण है कि वास्तविक क्रियान्वयन पिवट को randomise करते हैं या median-of-three का उपयोग करते हैं: ऐसा करने से सैद्धांतिक worst case हटता नहीं, पर वे साधारण, संभावित इनपुट हट जाते हैं जो पहले उसे ट्रिगर करते थे।

5. ग्राफ़ सिद्धांत के मूल तत्व एवं ग्राफ़ एल्गोरिथ्म: ट्रैवर्सल व न्यूनतम-पथ

ग्राफ़ शीर्षों (vertices) व उनके जोड़ों को जोड़ने वाली किनारों (edges) का समुच्चय है, जिसे या तो adjacency matrix (O(V²) स्थान, O(1) किनारा-खोज) या adjacency list (O(V+E) स्थान, तब बेहतर जब ग्राफ़ विरल हो — सामान्य स्थिति) के रूप में रखा जाता है। Breadth-first search (BFS) FIFO क्यू का उपयोग करते हुए स्तर-दर-स्तर खोजता है, दूरी k+1 के किसी भी शीर्ष से पहले दूरी k के हर शीर्ष पर जाता है; depth-first search (DFS) एक शाखा के साथ जितना संभव हो उतना दूर खोजता है, फिर वापस लौटता है, स्टैक (स्पष्ट या recursion के ज़रिए) का उपयोग करते हुए, और दूरी के बजाय संबद्धता (connectivity) व cycle पहचान हेतु स्वाभाविक औज़ार है।

ℹ️ BFS न्यूनतम-पथ मुफ़्त में देता है; DFS नहीं
चूँकि BFS स्रोत से बढ़ती दूरी (किनारों की संख्या) के सख्त क्रम में शीर्षों पर जाता है, वह किसी भी शीर्ष तक पहली बार जिस रास्ते पहुँचता है वही उसका न्यूनतम पथ है — यह केवल अभारित (unweighted) ग्राफ़ों के लिए सत्य है, जहाँ हर किनारा एक कदम गिना जाता है। DFS ऐसी कोई गारंटी बिलकुल नहीं देता: यह किसी शीर्ष तक एक लंबे, घुमावदार रास्ते से पहुँच सकता है जबकि ग्राफ़ में कहीं और एक कहीं छोटा रास्ता मौजूद हो, केवल इसलिए क्योंकि यह पहले गहराई में गया।

Dijkstra का एल्गोरिथ्म इसी विचार को भारित (weighted) ग्राफ़ों तक बढ़ाता है: यह बार-बार वह अभी-तक-अंतिम-न-हुआ शीर्ष चुनता है जिसकी स्रोत से ज्ञात दूरी सबसे कम है (priority queue का उपयोग करते हुए), उसे अंतिम करता है, और उसके हर पड़ोसी की दूरी को relax (अद्यतन) करता है। यह स्रोत से हर अन्य शीर्ष तक सही न्यूनतम-पथ खोजता है, बशर्ते हर किनारे का भार गैर-ऋणात्मक हो — 'ज्ञात निकटतम शीर्ष को अंतिम करो' का लालची (greedy) चरण तभी सुरक्षित है जब कोई बाद वाला किनारा किसी पहले-से-अंतिम शीर्ष की दूरी को घटा न सके, जिसे कोई ऋणात्मक किनारा-भार भंग कर सकता है।

मुख्य बिंदु

  • स्टैक LIFO हैं, O(1) push/pop सहित; क्यू FIFO हैं — पर pop(0) के ज़रिए क्यू की तरह उपयोग की गई Python list प्रति कॉल O(n) है, O(1) नहीं, क्योंकि आगे से हटाने हेतु list अवयवों को खिसकाती है।
  • लिंक्ड लिस्ट किसी ज्ञात नोड पर O(1) सम्मिलन/विलोपन के बदले स्थिति से O(n) एक्सेस देती है; हैश टेबल कुंजी से औसत-स्थिति O(1) एक्सेस देती है पर collision ढेर होने पर इसका worst case O(n) तक बिगड़ता है।
  • Binary search को क्रमबद्ध डेटा चाहिए और यह O(log n) में चलता है; insertion sort worst case में O(n²) है पर लगभग-क्रमबद्ध इनपुट पर O(n), यही कारण है कि यह छोटी या लगभग-क्रमबद्ध ऐरे पर asymptotically तेज़ सॉर्ट्स को भी मात दे देता है।
  • Mergesort सदा Θ(n log n) है पर इसे O(n) अतिरिक्त स्थान चाहिए; quicksort in-place है व औसतन Θ(n log n) पर पहले-से-क्रमबद्ध ऐरे पर Θ(n²) तक बिगड़ जाता है जब तक पिवट यादृच्छिक या median-of-three से न चुना जाए।
  • BFS शीर्षों पर दूरी के क्रम में जाता है और अभारित ग्राफ़ों में न्यूनतम-पथ खोजता है; Dijkstra का एल्गोरिथ्म इसे गैर-ऋणात्मक किनारा-भारों तक सामान्यीकृत करता है, और जैसे ही कोई ऋणात्मक किनारा-भार अनुमत हो, इसका लालची चरण असुरक्षित हो जाता है।

अभ्यास प्रश्न (13)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. Python में, क्यू लागू करने हेतु बार-बार list.pop(0) बुलाने की प्रति-कॉल समय जटिलता क्या है?

    1. O(1)
    2. O(log n)
    3. O(n)
    4. O(n²)
    उत्तर देखें

    उत्तर: C — O(n)

    Python list के पहले अवयव को हटाने हेतु शेष हर अवयव को एक स्थान बाईं ओर खिसकाना पड़ता है, जो O(n) है; deque वह संरचना है जो आगे से O(1) हटाने हेतु बनी है।

  2. कौन-सी डेटा संरचना स्वाभाविक रूप से वह LIFO क्रम लागू करती है जो फ़ंक्शन-कॉल recursion के आधार में है?

    1. क्यू
    2. स्टैक
    3. हैश टेबल
    4. बाइनरी सर्च ट्री
    उत्तर देखें

    उत्तर: B — स्टैक

    हर recursive कॉल का फ़्रेम कॉल-स्टैक पर push होता है और उस कॉल के लौटने पर pop होता है, जो ठीक LIFO क्रम है।

  3. chaining द्वारा collision सुलझाने वाली हैश टेबल के बारे में निम्न में से कौन-से सत्य हैं?

    1. अच्छे हैश फ़ंक्शन व उचित load factor के साथ, औसत-स्थिति खोज O(1) है
    2. worst-case खोज सदा O(1) है, चाहे कितनी भी कुंजियाँ टकराएँ
    3. load factor को एक बिंदु से आगे बढ़ाना हर स्लॉट पर औसत chain-लंबाई बढ़ाता है
    4. यदि टेबल पर्याप्त बड़ी हो तो दो भिन्न कुंजियाँ कभी एक ही इंडेक्स पर हैश नहीं हो सकतीं
    उत्तर देखें

    उत्तर: A — अच्छे हैश फ़ंक्शन व उचित load factor के साथ, औसत-स्थिति खोज O(1) है; C — load factor को एक बिंदु से आगे बढ़ाना हर स्लॉट पर औसत chain-लंबाई बढ़ाता है

    औसत-स्थिति O(1) ही हैश टेबल का पूरा उद्देश्य है, पर जब कई कुंजियाँ एक ही chain में टकराएँ तो worst case O(n) तक बिगड़ता है; बड़ी टेबल टकराव की संभावना घटाती है पर कभी समाप्त नहीं करती, क्योंकि जब कुंजियाँ उपलब्ध स्लॉट से अधिक हो जाएँ तो कबूतरखाना सिद्धांत (pigeonhole principle) तब भी लागू रहता है।

  4. किसी ऐरे पर binary search हेतु आवश्यक है कि ऐरे पहले से

    1. क्रमबद्ध हो
    2. लिंक्ड लिस्ट के रूप में संग्रहित हो
    3. सम लंबाई की हो
    4. हैश टेबल में हैश की गई हो
    उत्तर देखें

    उत्तर: A — क्रमबद्ध हो

    Binary search यह तय करता है कि कौन-सा आधा त्यागना है लक्ष्य की मध्य अवयव से तुलना करके; यह तुलना तभी कुछ उपयोगी बताती है जब ऐरे पहले से क्रमबद्ध हो।

  5. insertion sort की best-case समय जटिलता, जो पहले-से-क्रमबद्ध ऐरे पर मिलती है, है

    1. O(n)
    2. O(n log n)
    3. O(n²)
    4. O(log n)
    उत्तर देखें

    उत्तर: A — O(n)

    पहले-से-क्रमबद्ध ऐरे पर, हर नए अवयव को ठीक पहले वाले अवयव से केवल एक तुलना चाहिए और बिलकुल कोई खिसकाव नहीं, जो कुल मिलाकर O(n) देता है।

  6. अपने मानक क्रियान्वयन में, selection sort इनपुट के क्रम से निरपेक्ष सदा उतनी ही तुलनाएँ करता है। n = 5 अवयवों की ऐरे पर यह कितनी तुलनाएँ करता है?

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 10

    Selection sort हर पास का न्यूनतम खोजने हेतु सदा n(n-1)/2 तुलनाएँ करता है, आरंभिक क्रम से निरपेक्ष; n = 5 के लिए यह 5×4/2 = 10 है।

  7. कौन-सा सॉर्टिंग एल्गोरिथ्म worst case व average case दोनों में Θ(n log n) समय में चलता है, O(n) अतिरिक्त स्थान की क़ीमत पर?

    1. Quicksort
    2. Mergesort
    3. Insertion sort
    4. Selection sort
    उत्तर देखें

    उत्तर: B — Mergesort

    Mergesort डेटा से निरपेक्ष ऐरे को सदा समान रूप से बाँटता है, अतः इसका worst व average case दोनों Θ(n log n) हैं; merge चरण को O(n) सहायक स्थान चाहिए।

  8. Quicksort अपने Θ(n²) worst case तक पहले-से-क्रमबद्ध ऐरे पर तब बिगड़ता है जब पिवट चुना जाता है

    1. हर बार एक यादृच्छिक रूप से चुना गया अवयव
    2. तीन नमूना अवयवों का माध्यक (median)
    3. पहला अवयव, हर बार
    4. हर recursive कॉल पर एक भिन्न यादृच्छिक स्थिति
    उत्तर देखें

    उत्तर: C — पहला अवयव, हर बार

    पहले-से-क्रमबद्ध ऐरे पर सदा पहला अवयव लेना उसे मौजूद सबसे छोटा बना देता है, अतः हर विभाजन शेष सभी n-1 अवयवों को एक ओर रख देता है, जो हर चरण में सर्वाधिक असंतुलित विभाजन देता है।

  9. किसी अभारित ग्राफ़ में किसी स्रोत शीर्ष से आरंभ करके, कौन-सा ट्रैवर्सल हर पहुँच-योग्य शीर्ष तक न्यूनतम-पथ (सबसे कम किनारे) खोजने की गारंटी देता है?

    1. गहराई-प्रथम खोज (DFS)
    2. चौड़ाई-प्रथम खोज (BFS)
    3. दोनों समान रूप से
    4. किनारा-भार दर्ज किए बिना कोई नहीं
    उत्तर देखें

    उत्तर: B — चौड़ाई-प्रथम खोज (BFS)

    BFS स्रोत से बढ़ती दूरी के सख्त क्रम में शीर्षों पर जाता है, अतः यह किसी भी शीर्ष तक जिस पहली बार पहुँचता है वह किसी अभारित ग्राफ़ में अनिवार्यतः न्यूनतम-पथ से होता है।

  10. Dijkstra का एल्गोरिथ्म ग़लत न्यूनतम-पथ परिणाम दे सकता है ऐसे ग्राफ़ पर जिसमें हो

    1. एक cycle
    2. शून्य भार का किनारा
    3. ऋणात्मक-भार किनारा
    4. एक ही जोड़े शीर्षों के बीच एक से अधिक किनारे
    उत्तर देखें

    उत्तर: C — ऋणात्मक-भार किनारा

    Dijkstra का लालची चरण निकटतम ज्ञात शीर्ष को अंतिम करता है और उसे दोबारा नहीं देखता; बाद में कोई ऋणात्मक-भार किनारा उस तक के पथ को छोटा कर सकता था, जिसे उस शीर्ष के अंतिम होने के बाद एल्गोरिथ्म खोज नहीं सकता।

  11. adjacency list के रूप में संग्रहित ग्राफ़ पर, binary-heap priority queue से लागू Dijkstra का एल्गोरिथ्म चलता है

    1. O(V²)
    2. O(V + E)
    3. O((V + E) log V)
    4. किनारों को पूर्णतः अनदेखा करते हुए अकेला O(V log V)
    उत्तर देखें

    उत्तर: C — O((V + E) log V)

    E किनारों में से हर एक किसी binary heap पर O(log V) लागत वाला decrease-key/insert संचालन ट्रिगर कर सकता है, और V शीर्षों में से हर एक को O(log V) पर एक बार निकाला जाता है, जो कुल मिलाकर O((V + E) log V) देता है।

  12. एक बाइनरी सर्च ट्री जो एक सीधी शृंखला में बिगड़ चुका है, जहाँ हर नोड की केवल एक संतान है, कैसा खोज-समय देता है

    1. O(log n)
    2. O(n)
    3. O(n log n)
    4. O(1)
    उत्तर देखें

    उत्तर: B — O(n)

    शृंखला में बिगड़ा ट्री गहराई n रखता है, अतः किसी खोज को हर नोड से ठीक उसी तरह गुज़रना पड़ सकता है जैसे लिंक्ड लिस्ट में, जो किसी संतुलित ट्री के O(log n) के बजाय O(n) देता है।

  13. निम्न में से कौन-से सॉर्टिंग एल्गोरिथ्म अपने मानक क्रियान्वयन में stable हैं (बराबर अवयव अपना सापेक्ष क्रम बनाए रखते हैं)?

    1. Mergesort
    2. मानक (in-place) quicksort
    3. Insertion sort
    4. Selection sort
    उत्तर देखें

    उत्तर: A — Mergesort; C — Insertion sort

    Mergesort के merge चरण व insertion sort के खिसकाव दोनों बराबर अवयवों का मूल क्रम बनाए रखते हैं; मानक in-place quicksort का विभाजन व selection sort के लंबी-दूरी के स्वैप इसकी गारंटी नहीं देते।