“आज के हर स्मार्टफोन में चंद्रमा पर अंतरिक्ष यात्रियों को पहुँचाने वाले कंप्यूटरों की तुलना में हजारों गुना अधिक प्रोसेसिंग शक्ति होती है।”

$\quad$ - पीटर थील

5.1 परिचय

छँटाई (sorting) किसी दी गई तत्वों की संग्रह को किसी विशेष क्रम में व्यवस्थित करने की प्रक्रिया है। हम संख्याओं के संग्रह को आरोही (बढ़ते) या अवरोही (घटते) क्रम में छाँट सकते हैं। यदि संग्रह स्ट्रिंग्स का है, तो हम इसे वर्णमाला क्रम में ($a-z$ या $z-a$) या स्ट्रिंग की लंबाई के अनुसार छाँट सकते हैं। उदाहरण के लिए, शब्दकोश में शब्द वर्णमाला क्रम में होते हैं; परीक्षा हॉल में सीटें उम्मीदवारों के रोल नंबर के अनुसार व्यवस्थित होती हैं। हम छात्रों की सूची को उनकी ऊँचाई या वजन के आधार पर भी छाँट सकते हैं।

कल्पना कीजिए कि आपको किसी ऐसे शब्दकोश से किसी शब्द का अर्थ खोजना है जो क्रमबद्ध नहीं है। हमें वह शब्द मिलने तक हर पृष्ठ पर खोजना होगा, जो बहुत ही थकाऊ होगा। इसीलिए शब्दकोशों में शब्द वर्णमाला क्रम में होते हैं और यह खोज की प्रक्रिया को आसान बनाता है।

सोचिए और विचार कीजिए

क्या आप अन्य उदाहरण पहचान सकते हैं जहाँ कंप्यूटरों में छँटाई एक महत्वपूर्ण भूमिका निभाती है?

बड़ी संख्या में आइटमों को सॉर्ट करने में काफी समय लग सकता है। हालाँकि, यह अतिरिक्त समय (जिसे ओवरहेड कहा जाता है) एक असॉर्टेड सूची से किसी तत्व को खोजने में लगने वाले समय की तुलना में सार्थक साबित होता है। सॉर्टिंग कंप्यूटर विज्ञान का एक महत्वपूर्ण अध्ययन क्षेत्र है, और कई सॉर्टिंग एल्गोरिद्म विकसित किए गए हैं और उनके प्रदर्शन के दृष्टिकोण से विश्लेषण किया गया है। इस अध्याय में, हम तीन सॉर्टिंग विधियों के बारे में सीखेंगे और उन्हें Python का उपयोग करके लागू करेंगे। बबल सॉर्ट की चर्चा अनुभाग 5.2 में की गई है, जिसके बाद अनुभाग 5.3 और 5.4 में क्रमशः सिलेक्शन सॉर्ट और इंसर्शन सॉर्ट पर चर्चा की गई है।

5.2 बबल सॉर्ट

हम जिस पहले सॉर्टिंग तकनीक को समझने जा रहे हैं वह बबल सॉर्ट है। यह दिए गए तत्वों की सूची को बार-बार आसन्न तत्वों की तुलना करके और यदि वे अक्रमित हों तो उन्हें स्वैप करके सॉर्ट करता है। दो तत्वों को स्वैप करना का अर्थ है उनकी स्थितियों को आपस में बदलना। एल्गोरिद्म में, सूची के प्रत्येक तत्व से गुजरने वाली हर पुनरावृत्ति को एक पास कहा जाता है। $\mathrm{n}$ तत्वों वाली सूची के लिए, बबल सॉर्ट सूची को सॉर्ट करने के लिए कुल $n-1$ पास बनाता है। प्रत्येक पास में, सूची के आसन्न तत्वों के आवश्यक युग्मों की तुलना की जाएगी। तत्वों को आरोही क्रम में व्यवस्थित करने के लिए, प्रत्येक पास के बाद सबसे बड़ा तत्व पहचाना जाता है और सूची में सही स्थिति पर रखा जाता है। इसे सबसे बड़े तत्व के ‘बबल अप’ होने के रूप में माना जा सकता है। इसलिए इसका नाम बबल सॉर्ट है। यह सॉर्टेड तत्व शेष पासों में विचार में नहीं लिया जाता है और इस प्रकार तत्वों की सूची क्रमिक पासों में घटती जाती है।

सोचिए और विचार कीजिए

चित्र 5.1 में, हम देख सकते हैं कि सूची 4वें पास में ही सॉर्ट हो गई। फिर भी बबल सॉर्ट तकनीक ने एक अनावश्यक 5वां पास बनाया जिससे कोई स्वैप नहीं हुआ। यदि किसी पास में कोई स्वैप नहीं होता है, तो इसका अर्थ है कि सूची पहले से ही सॉर्टेड है, इसलिए सॉर्टिंग संचालन को रोकना चाहिए। क्या आप एल्गोरिद्म 5.1 में कोई सुधार करने के बारे में सोच सकते हैं ताकि यह तब रुक जाए जब सूची सॉर्ट हो जाए?

चित्र 5.1 बबल सॉर्ट विधि द्वारा सूची को आरोही क्रम में व्यवस्थित करने की कार्यप्रणाली को दर्शाता है। आइए एक ऐसी सूची पर विचार करें जिसमें 6 तत्व हैं: numList $=[8$, $7,13,1,-9,4]$। चित्र में, तुलना किए जा रहे तत्वों को नीले रंग से और सॉर्ट किए गए तत्वों को हरे रंग से हाइलाइट किया गया है। सॉर्टिंग शुरू करने के लिए, सूचकांक 0 पर स्थित तत्व की तुलना सूचकांक 1 पर स्थित तत्व से की जाती है। यदि पहला तत्व बड़ा है, तो इसे दूसरे तत्व से स्वैप कर दिया जाता है। अन्यथा, कोई परिवर्तन नहीं किया जाता है। इसके बाद, सूचकांक 1 पर स्थित तत्व की तुलना सूचकांक 2 पर स्थित तत्व से की जाती है। यह प्रक्रिया सूची के अंत तक जारी रहती है। पहले पास के बाद, सबसे बड़ा तत्व सूची के अंत तक पहुँच जाता है, जैसा कि चित्र 5.1 में हरे रंग से दिखाया गया है।

चित्र 5.1: बबल सॉर्ट के विभिन्न पासों में की गई तुलनाएँ

गतिविधि 5.1

एल्गोरिद्म 5.1 एक सूची को आरोही क्रम में सॉर्ट करता है। एक बबल सॉर्ट एल्गोरिद्म लिखिए जो सूची को अवरोही क्रम में सॉर्ट करे?

एल्गोरिद्म 5.1 उन चरणों को दर्शाता है जो बबल सॉर्ट के लिए अपनाए जाते हैं, जो numList को $n$ तत्वों की सूची के रूप में लेता है और सूची को आरोही क्रम में सॉर्ट करता है:

एल्गोरिद्म 5.1: बबल सॉर्ट

BUBBLESORT( numList, n)
चरण 1: SET i = 0
चरण 2: WHILE i< n REPEAT STEPS 3 to 8
चरण 3: SET j = 0
चरण 4: WHILE j< n-i-1,REPEAT STEPS 5 to 7
चरण 5: $\quad$ IF numList[j] > numList[j+1] THEN
चरण 6: $\qquad$ swap(numList[j],numList[j+1])
चरण 7: $\quad$ SET j=j+1
चरण 8: SET i=i+1

प्रोग्राम 5-1 बबल सॉर्ट का पायथन में कार्यान्वयन.

def bubble_Sort(list1):
$\quad$ n = len(list1)
$\quad$ for i in range(n): $\quad$ # पासों की संख्या
$\qquad$ for j in range(0, n-i-1):
$\qquad$ #size -i-1 क्योंकि अंतिम i तत्व पहले ही क्रमबद्ध हो चुके हैं
$\hspace{1cm}$ #पिछले पासों में
$\hspace{1.5cm}$ if list1[j] > list1[j+1] :
$\hspace{1.5cm}$ #jवें स्थान के तत्व को (j+1)वें स्थान के तत्व से बदलना
$\hspace{2cm}$ list1[j], list1[j+1] = list1[j+1], list1[j]
numList = [8, 7, 13, 1, -9, 4]
bubble_Sort(numList)
print (“क्रमबद्ध सूची है :”)
for i in range(len(numList)):
$\quad$ print (numList[i], end=" “)

आउटपुट:

क्रमबद्ध सूची है :
-9 1 4 7 8 13

5.3 चयन सॉर्ट

चयन सॉर्ट एक अन्य क्रमबद्ध तकनीक है। n तत्वों वाली सूची को क्रमबद्ध करने के लिए, चयन सॉर्ट सूची में (n-1) संख्या में पास लगाता है। सूची को दो सूचियों में विभाजित माना जाता है – बाईं सूची में क्रमबद्ध तत्व होते हैं, और दाईं सूची में अक्रमबद्ध तत्व होते हैं। प्रारंभ में, बाईं सूची खाली होती है, और दाईं सूची में सभी तत्व होते हैं।

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

यह प्रक्रिया तब तक जारी रहती है जब तक $\mathrm{n}-1$ सबसे छोटे तत्व मिल न जाएं और अपने-अपने स्थानों पर न चले जाएं। nth तत्व अंतिम है, और यह पहले से ही अपने स्थान पर है। चित्र 5.2 आरोही क्रम में सूची को व्यवस्थित करने के लिए चयन सॉर्ट विधि के कार्य को प्रदर्शित करता है। इस चित्र में, तीरों का उपयोग करके तुलना किए जा रहे तत्वों को दिखाया गया है और तुलना में छोटा तत्व नीले रंग से हाइलाइट किया गया है। सॉर्टेड तत्वों को हाइलाइट किया गया है-

गतिविधि 5.2

बबल सॉर्ट तकनीक लागू करें ताकि तत्वों की एक सूची numList 2 $=[8,7,6,5,4]$ को सॉर्ट किया जा सके। प्रत्येक पास के बाद सूची में तत्वों की स्थितियाँ दिखाएं। किस पास में अंतिम स्वैप होता है?

आकृति 5.2: चयन क्रम में विभिन्न पासों में किए गए तुलनाएँ

निम्नलिखित चयन क्रम के लिए एक एल्गोरिद्म है जो numList को n तत्वों वाली सूची के रूप में लेता है, और सूची को आरोही क्रम में क्रमबद्ध करता है:

एल्गोरिद्म 5.2 चयन क्रम के लिए अनुसरण किए जाने वाले चरणों को दिखाता है जो numList को n तत्वों की सूची के रूप में लेता है, और सूची को आरोही क्रम में क्रमबद्ध करता है:

एल्गोरिद्म 5.2: चयन क्रम

SELECTIONSORT( numList, n)
चरण 1: SET i=0
चरण 2: WHILE i< n REPEAT STEPS 3 to 11
चरण 3: $\quad$ SET min = i, flag = 0
चरण 4: $\quad$ SET j= i+1
चरण 5: $\quad$ WHILE j<n, REPEAT STEPS 6 to 10
चरण 6: $\qquad$ IF numList[j] < numList[min] THEN
चरण 7: $\hspace{1cm}$ min = j
चरण 8: $\hspace{1cm}$ flag = 1
चरण 9: $\qquad$ IF flag = 1 THEN
चरण 10: $\qquad$ swap(numList[i],numList[min])
चरण 11: SET i=i+1

गतिविधि 5.3

10 तत्वों की एक सूची पर विचार करें: randList $=$ $[7,11,3,10,17,23,1,4,21,5]$. चयन क्रम के चार पूर्ण पासों के बाद आंशिक रूप से क्रमबद्ध सूची निर्धारित करें।

प्रोग्राम 5-2 Python का उपयोग कर चयन क्रम का कार्यान्वयन।

def selection_Sort(list2):
    flag = 0	    #स्वैप करने का निर्णय लेने के लिए
    n=len(list2)
    for i in range(n):  #सभी सूची तत्वों के माध्यम से पार करें
        min = i
        for j in range(i + 1, len(list2)):	#बाएँ तत्व
        #पिछले पासों में पहले ही क्रमबद्ध हो चुके हैं
            if list2[j] < list2[min]:  #j पर तत्व न्यूनतम से छोटा है
            #वर्तमान न्यूनतम तत्व की तुलना में
                min = j
                flag = 1
        if flag == 1 : 	#अगला सबसे छोटा तत्व मिल गया
            list2[min], list2[i] = list2[i], list2[min]

numList = [8, 7, 13, 1, -9, 4]
selection_Sort(numList)
print ("The sorted list is :")
for i in range(len(numList)):
    print (numList[i], end=" ")

आउटपुट:

The sorted list is :
-9 1 4 7 8 13

5.4 इन्सर्शन सॉर्ट

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

पास 1 में, अनर्गित सूची में n-1 तत्व होते हैं और सॉर्टेड सूची में एक एकल तत्व होता है (मान लीजिए तत्व s)। अनर्गित सूची का पहला तत्व (मान लीजिए तत्व e) को सॉर्टेड सूची के तत्व s से तुलना किया जाता है। यदि तत्व e, तत्व s से छोटा है, तो तत्व s को दाईं ओर शिफ्ट किया जाता है ताकि तत्व e को डालने के लिए जगह बन सके। यह शिफ्टिंग अब सॉर्टेड सूची का आकार 2 और अनर्गित सूची का आकार n-2 कर देगी।

पास 2 में, अनर्गित सूची का पहला तत्व (मान लीजिए तत्व e) को सॉर्टेड सूची के प्रत्येक तत्व से पिछली दिशा से शुरू करते हुए तुलना किया जाएगा जब तक कि सम्मिलन के लिए उपयुक्त स्थान नहीं मिल जाता। सॉर्टेड सूची के तत्वों को दाईं ओर शिफ्ट किया जाएगा ताकि तत्व e को वहाँ डालने के लिए जगह बन सके जहाँ इसे सम्मिलित किया जा सके।

यह तब तक जारी रहता है जब तक कि अनर्गित सूचियों में सभी तत्व सॉर्टेड सूची में उपयुक्त स्थानों पर नहीं डाले जाते। इससे एक सॉर्टेड सूची प्राप्त होती है जिसमें तत्व आरोही क्रम में व्यवस्थित होते हैं।

आकृति 5.3 आरोही क्रम में सूची को व्यवस्थित करने के लिए सम्मिलन सॉर्ट के कार्य को प्रदर्शित करती है।

आकृति 5.3: सम्मिलन सॉर्ट के विभिन्न पासों में किए गए तुलनाएँ

मान लीजिए कि numList एक ऐसी सूची है जिसमें $\mathrm{n}$ तत्व हैं। एल्गोरिदम 5.3 insertion sort तकनीक का उपयोग करके numList सूची को आरोही क्रम में क्रमबद्ध करता है।

एल्गोरिदम 5.3: इन्सर्शन सॉर्ट

INSERTIONSORT( numList, n)
चरण 1: SET i=1
चरण 2: WHILE i< n दोहराएँ चरण 3 से 9
चरण 3: $\quad$ temp = numList[i]
चरण 4: $\quad$ SET j = i-1
चरण 5: $\quad$ WHILE j> = 0 और numList[j]>temp,चरण 6 से 7 दोहराएँ
चरण 6: $\qquad$ numList[j+1] = numList[j]
चरण 7: $\qquad$ SET j=j-1
चरण 8: $\quad$ numList[j+1] = temp $\quad$ #insert temp at position j
चरण 9: set i=i+1

गतिविधि 5.4

10 तत्वों की एक सूची पर विचार करें:

Array = [7,11,3,10,17,23,1,4,21,5] insertion sort के तीन पूर्ण पास के बाद आंशिक रूप से क्रमबद्ध सूची निर्धारित करें।

प्रोग्राम 5-3 Python का उपयोग कर insertion sort का कार्यान्वयन।

def insertion_Sort(list3):
$\quad$ for i in range(n): $\quad$ # सभी तत्वों के माध्यम से पार करें
$\quad$ n= len(list3)
$\qquad$ temp = list3[i]
$\qquad$ j = i-1
$\qquad$ while j >=0 और temp< list3[j] :
$\hspace{1cm}$ list3[j+1] = list3[j]
$\hspace{1cm}$ j = j-1
$\qquad$ list3[j+1] = temp

numList = [8, 7, 13, 1, -9, 4]
insertion_Sort(numList)
print (“The sorted list is :”)
for i in range(len(numList)):
$\quad$ print (numList[i], end=” “)

आउटपुट:

The sorted list is :
-9 1 4 7 8 1 3

5.5 एल्गोरिदमों की समय जटिलता

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

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

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

विभिन्न एल्गोरिदमों की जटिलता की गणना में गणितीय गणनाएँ और विस्तृत विश्लेषण शामिल होता है, और इस पाठ्यपुस्तक की सीमा में उनकी विस्तृत चर्चा करना संभव नहीं है। फिर भी, हम जटिलता की कुछ बुनियादी बातों पर चर्चा करेंगे ताकि कुछ विचार प्राप्त हो सकें। निम्नलिखित सुझाव हमें किसी एल्गोरिदम की समय जटिलता का आकलन करने में मार्गदर्शन करेंगे।

• कोई भी एल्गोरिदम जिसमें कोई लूप नहीं है, उसकी समय जटिलता 1 होगी क्योंकि निष्पादित होने वाले निर्देशों की संख्या डेटा के आकार के बावजूद स्थिर रहेगी। ऐसे एल्गोरिदमों को स्थिर समय एल्गोरिदम (Constant time algorithms) कहा जाता है।
• कोई भी एल्गोरिदम जिसमें एक लूप है (आमतौर पर 1 से $\mathrm{n}$ तक), उसकी समय जटिलता $n$ होगी क्योंकि लूप अपने भीतर के कथन को $n$ बार निष्पादित करेगा। ऐसे एल्गोरिदमों को रैखिक समय एल्गोरिदम (Linear time algorithms) कहा जाता है।
• एक लूप के भीतर एक और लूप (नेस्टेड लूप) की समय जटिलता $n^{2}$ होगी। ऐसे एल्गोरिदमों को द्विघात समय एल्गोरिदम (Quadratic time algorithms) कहा जाता है।
• यदि एक नेस्टेड लूप के साथ-साथ एक अकेला लूप भी है, तो समय जटिलता का आकलन केवल नेस्टेड लूप के आधार पर किया जाएगा।

अब, इस अध्याय में चर्चा किए गए तीन सॉर्टिंग तकनीकों के Python प्रोग्रामों को देखें, आप देखेंगे कि तीनों प्रोग्रामों में एक नेस्टेड लूप है, यानी एक लूप दूसरे के भीतर है। तो उपरोक्त नियमों के अनुसार, सभी सॉर्टिंग एल्गोरिदम—बबल सॉर्ट, सेलेक्शन सॉर्ट और इंसर्शन सॉर्ट—की समय जटिलता $n^{2}$ है।

सारांश

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

अभ्यास

1. 10 तत्वों की एक सूची पर विचार करें:

numList = [7,11,3,10,17,23,1,4,21,5]। बबल सॉर्ट के तीन पूर्ण पासों के बाद आंशिक रूप से सॉर्टेड सूची प्रदर्शित करें।

2. निम्नलिखित सूची को सिलेक्शन सॉर्ट और बबल सॉर्ट का उपयोग करके सॉर्ट करने के लिए आवश्यक स्वैपों की संख्या पहचानें और यह पहचानें कि तुलनाओं की संख्या के संदर्भ में कौन-सी सॉर्टिंग तकनीक बेहतर है।

सूची 1 : $\begin{array}{|l|l|l|l|l|} \hline 63 & 42 & 21 & 9 \\ \hline \end{array}$

3. निम्नलिखित सूचियों पर विचार करें:

सूची 1: $\begin{array}{|l|l|l|l|l|l|} \hline 2 & 7 & 5 & 7 & 11 \\ \hline \end{array}$

सूची 2: $\begin{array}{|l|l|l|l|l|l|} \hline 11 & 7 & 5 & 3 & 2 \\ \hline \end{array}$

यदि सूचियों को इन्सर्शन सॉर्ट द्वारा क्रमबद्ध किया जाता है तो सूची 1 या सूची 2 में से कौन-सी सूची न्यूनतम तुलनाएँ करेगी? आरेखीय प्रस्तुति द्वारा औचित्य दीजिए।

4. एक ऐसा कार्यक्रम लिखिए जो उपयोगकर्ता-परिभाषित फलनों का प्रयोग करता हो, जो संख्याओं की एक सूची को तर्क के रूप में स्वीकार करे और उसका माध्यिका (median) निकाले। (संकेत : स्वीकृत सूची को बबल सॉर्ट द्वारा क्रमबद्ध करें। यदि विषम संख्या में पद हों तो माध्यिका मध्य पद होता है। यदि सम संख्या में पद हों तो दो मध्य पदों को जोड़कर 2 से भाग देने पर माध्यिका प्राप्त होता है)

5. XYZ स्कूल की सभी शाखाओं ने आयु वर्ग $14-16$ के सभी विद्यार्थियों के लिए एक अभिरुचि परीक्षा आयोजित की। कुल $n$ विद्यार्थी थे। $n$ विद्यार्थियों के अंक एक सूची में संग्रहित हैं। एक ऐसा कार्यक्रम लिखिए जो उपयोगकर्ता-परिभाषित फलन का प्रयोग करता हो, जो अंकों की एक सूची को तर्क के रूप में स्वीकार करे और ‘$\mathrm{x}^{\mathrm{th}}$’ प्रतिशत (percentile) की गणना करे (जहाँ $\mathrm{x}$ 0 और 100 के बीच कोई संख्या है)। ‘$x^{\text {th}}$’ प्रतिशत की गणना करने के लिए आपको निम्नलिखित चरणों का पालन करना होगा।

नोट: प्रतिशत एक सापेक्ष प्रदर्शन का माप है, अर्थात् यह किसी उम्मीदवार के प्रदर्शन को दूसरों के सापेक्ष गणना करता है। उदाहरण : यदि किसी उम्मीदवार का स्कोर $90^{\text {th}}$ प्रतिशत में है, तो इसका अर्थ है कि उसने परीक्षा देने वाले $90 %$ लोगों से बेहतर स्कोर किया है।

$\mathrm{x}^{\text {th}}$ प्रतिशत की गणना के चरण:

I. डेटा सेट में सभी मानों को सबसे छोटे से सबसे बड़े तक क्रमबद्ध करें Selection Sort का उपयोग करके। सामान्यतः कोई भी क्रमबद्ध करने की विधि उपयोग की जा सकती है।

II. सूचकांक की गणना करें x प्रतिशत को कुल मानों की संख्या n से गुणा करके। उदाहरण के लिए: 120 छात्रों के लिए 90वां प्रतिशतक निकालने के लिए:

$$ 0.90 * 120=108 $$

III. math.round() का उपयोग करके सुनिश्चित करें कि सूचकांक एक पूर्ण संख्या है।

VI. चरण 3 में प्राप्त सूचकांक पर स्थित मान को प्रदर्शित करें।

सूची में संगत मान ही xवां प्रतिशतक है।

6. किसी पाठ्यक्रम में प्रवेश के समय छात्रों के नाम आरोही क्रम में डाले जाते हैं। इस प्रकार, सूची में तत्व डालते समय ही क्रमबद्ध करने की प्रक्रिया की जाती है। प्रयुक्त क्रमबद्ध करने की तकनीक की पहचान करें और एक उपयोगकर्ता-परिभाषित फ़ंक्शन का उपयोग करते हुए एक कार्यक्रम लिखें जो हर बार जब कोई नाम इनपुट किया जाता है तब आह्वान होता है और नाम को नामों के आरोही क्रम में सूची में संग्रहित करता है।