होम › मुफ़्त नोट्स › कक्षा 12 कंप्यूटर विज्ञान › सॉर्टिंग

सॉर्टिंग – कक्षा 12 कंप्यूटर विज्ञान नोट्स, महत्वपूर्ण प्रश्न और MCQ

NCERT कक्षा 12 कंप्यूटर विज्ञान, अध्याय 5। नोट्स, मुख्य शब्द, उत्तर सहित महत्वपूर्ण प्रश्न और MCQ।

अध्याय का सार

Sorting elements को किसी विशेष क्रम, आरोही या अवरोही, में व्यवस्थित करने की प्रक्रिया है। Sorted data searching और विश्लेषण को तेज़ बनाता है। इस अध्याय में तीन सरल sorting algorithms शामिल हैं: bubble sort, selection sort और insertion sort। प्रत्येक passes में कार्य करता है और worst case में O(n²) time complexity रखता है, जिसका विश्लेषण comparisons और swaps गिनकर होता है।

Bubble sort और selection sort

Bubble sort बार-बार adjacent elements की तुलना करता है और ग़लत क्रम में होने पर उन्हें swap करता है; प्रत्येक pass के बाद शेष सबसे बड़ा element अंत में अपनी सही स्थिति पर पहुँचता है। n elements की list को अधिकतम n − 1 passes चाहिए, और किसी pass में कोई swap न होने पर प्रक्रिया जल्दी रुक सकती है।
Selection sort list को sorted भाग और unsorted भाग में बाँटता है; प्रत्येक pass में यह unsorted भाग से सबसे छोटा element चुनकर पहले unsorted element से swap करता है।
Selection sort अधिकतम n − 1 swaps करता है, जबकि bubble sort अनेक swaps कर सकता है।

Insertion sort और complexity

Insertion sort unsorted भाग से elements एक-एक कर लेता है और बड़े elements को दाईं ओर खिसकाकर प्रत्येक को sorted भाग में सही स्थान पर डालता है, जैसे हाथ में ताश के पत्ते सजाना।
Time complexity बताती है कि input size n के साथ running time कैसे बढ़ता है; constant O(1), linear O(n), quadratic O(n²); तीनों algorithms worst case में O(n²) हैं, जबकि early-exit जाँच वाला bubble sort और insertion sort पहले से sorted list पर O(n) लेते हैं।
Python के built-in sort() और sorted() एक कुशल algorithm (Timsort) का प्रयोग करते हैं, पर सरल algorithms सीखना algorithm design समझने में मदद करता है।

मुख्य शब्द

Sorting: elements को विशिष्ट क्रम में व्यवस्थित करना
Bubble sort: ग़लत क्रम वाले adjacent elements को बार-बार swap करना
Selection sort: बार-बार सबसे छोटा element चुनकर स्थान पर रखना
Insertion sort: प्रत्येक element को sorted भाग में सही स्थान पर डालना
Time complexity: input size के साथ running time की वृद्धि का माप

उत्तर सहित महत्वपूर्ण प्रश्न

Time complexity क्या है?2 अंक

Time complexity इस बात का माप है कि input (n) का आकार बढ़ने पर algorithm का running time कैसे बढ़ता है। इसे Big-O notation में व्यक्त किया जाता है, जैसे constant time हेतु O(1), linear time हेतु O(n) और quadratic time हेतु O(n²)।

Bubble sort का Python code लिखिए।3 अंक

def bubble_sort(L): n = len(L); for i in range(n - 1): for j in range(n - 1 - i): if L[j] > L[j + 1]: L[j], L[j + 1] = L[j + 1], L[j]। प्रत्येक outer pass के बाद शेष सबसे बड़ा element अंत में अपनी सही स्थिति पर पहुँचता है।

Insertion sort को उदाहरण और Python implementation सहित समझाइए।5 अंक

Insertion sort एक समय में एक element से sorted list बनाता है। List को sorted भाग, प्रारंभ में केवल पहला element, और unsorted भाग वाला माना जाता है। Unsorted भाग से प्रत्येक element लेकर sorted भाग के elements से दाएँ से बाएँ तुलना की जाती है; बड़े elements एक स्थान दाईं ओर खिसकाए जाते हैं, और लिया गया element रिक्त स्थान में डाला जाता है। उदाहरण: [8, 3, 5, 1] को sort करें। Pass 1: 3 लें, 8 को दाएँ खिसकाएँ, 3 डालें, [3, 8, 5, 1] मिलता है। Pass 2: 5 लें, 8 को दाएँ खिसकाएँ, 3 छोटा है, इसलिए 5 डालें, [3, 5, 8, 1] मिलता है। Pass 3: 1 लें, 8, 5 और 3 को दाएँ खिसकाएँ, 1 को आरंभ में डालें, [1, 3, 5, 8] मिलता है। Python implementation: def insertion_sort(L): for i in range(1, len(L)): key = L[i]; j = i - 1; while j >= 0 and L[j] > key: L[j + 1] = L[j]; j = j - 1; फिर L[j + 1] = key। Worst case में, जब list उल्टे क्रम में हो, प्रत्येक element की सभी पिछले elements से तुलना होती है, जिससे O(n²) time complexity मिलती है। Best case में, जब list पहले से sorted हो, प्रति element केवल एक तुलना होती है, जिससे O(n) मिलता है। Insertion sort छोटी या लगभग sorted lists हेतु कुशल है और stable है, यानी समान elements अपना मूल क्रम बनाए रखते हैं।

त्वरित पुनरावृत्ति

Sorting की आवश्यकता।
Bubble sort passes और swaps।
Selection sort और insertion sort।
Time complexity: O(1), O(n), O(n²)।

परीक्षा सुझाव

[5, 2, 8, 1] पर प्रत्येक algorithm का pass by pass अनुरेखण करें।
याद रखें: तीनों worst case में O(n²) हैं।

अभ्यास MCQ

Elements को आरोही या अवरोही क्रम में व्यवस्थित करना है
1. sorting
2. searching
3. hashing
4. केवल merging
उत्तर देखें
उत्तर: (a) sorting. यह searching तेज़ बनाता है।
Adjacent elements की तुलना और swap करने वाली sorting विधि है
1. selection sort
2. insertion sort
3. bubble sort
4. binary sort
उत्तर देखें
उत्तर: (c) bubble sort. बड़े elements अंत की ओर बुलबुले की तरह जाते हैं।
Worst case में bubble sort की time complexity है
1. O(1)
2. O(n²)
3. O(log n)
4. O(n)
उत्तर देखें
उत्तर: (b) O(n²). List पर nested passes।
बार-बार न्यूनतम element खोजकर आरंभ में रखने वाला sort है
1. bubble sort
2. insertion sort
3. selection sort
4. quick sort
उत्तर देखें
उत्तर: (c) selection sort. यह सबसे छोटा element चुनता है।
n elements हेतु bubble sort को अधिकतम कितने passes चाहिए
1. n − 1
2. n
3. n + 1
4. 2n
उत्तर देखें
उत्तर: (a) n − 1. अंतिम element स्वतः स्थान पर आ जाता है।
ताश के पत्तों को एक-एक कर सही स्थान पर सजाना किसके समान है
1. selection sort
2. insertion sort
3. bubble sort
4. binary search
उत्तर देखें
उत्तर: (b) insertion sort. प्रत्येक पत्ता sorted भाग में डाला जाता है।
[5, 1, 4, 2] पर bubble sort (आरोही) के पहले pass के बाद list है
1. [1, 4, 2, 5]
2. [1, 5, 4, 2]
3. [1, 2, 4, 5]
4. [5, 4, 2, 1]
उत्तर देखें
उत्तर: (a) [1, 4, 2, 5]. सबसे बड़ा element 5 अंत में जाता है।
[7, 3, 9, 1] पर selection sort (आरोही) के पहले pass के बाद list है
1. [1, 3, 9, 7]
2. [3, 7, 9, 1]
3. [1, 7, 9, 3]
4. [3, 7, 1, 9]
उत्तर देखें
उत्तर: (a) [1, 3, 9, 7]. 1 को 7 से swap किया जाता है।

सभी अध्याय: कक्षा 12 कंप्यूटर विज्ञान

यह सामग्री Kundali IQ ने पुनरावृत्ति में मदद हेतु मानक, स्थापित तथ्यों से लिखी है। यह NCERT का आधिकारिक प्रकाशन नहीं है; अपनी पाठ्यपुस्तक भी अवश्य पढ़ें।