Python एल्गोरिदम

Python में Selection Sort

हर चरण में सबसे छोटा बचा element सही स्थान पर रखें।

  • मध्यम
  • 2 मिनट में पढ़ें
  • 1 चलाने योग्य उदाहरण

में Selection Sort क्या है?

समस्या क्या है

कुछ sorting एल्गोरिदम कम से कम आइटम हिलाने की कोशिश करते हैं, जो तब मायने रखता है जब किसी आइटम को हिलाना महँगा हो। Selection sort bubble sort से अलग तरीका दिखाता है: पहले सही आइटम ढूँढिए, फिर उसे एक बार में हिलाइए।

ऐसे समझें

Selection sort ऐसा है जैसे लंबाई के हिसाब से टीम चुनना। आप इंतज़ार कर रहे सभी लोगों को देखते हैं, सबसे छोटे को बुलाते हैं, और उसे लाइन की अगली जगह पर खड़ा कर देते हैं। फिर बाकी लोगों में अगला सबसे छोटा ढूँढते हैं, जब तक कोई न बचे।

टीम चुनने से कोड तक
for start in range(len(result)):📍 लाइन की अगली खाली जगह
minimum = start🤔 मान लीजिए यही सबसे छोटा है
result[index] < result[minimum]🔎 बाकी लोगों में किसी छोटे को ढूँढिए
result[start], result[minimum] = ...🔄 सबसे छोटे को खाली जगह पर लाइए
पूरे unsorted हिस्से को देखने के बाद हर जगह के लिए एक swap।
एक वाक्य में

Selection sort बार-बार लिस्ट के unsorted हिस्से में सबसे छोटा आइटम ढूँढता है और उसे sorted हिस्से की अगली जगह पर swap कर देता है। इसमें O(n²) तुलनाएँ लगती हैं, लेकिन ज़्यादा से ज़्यादा n - 1 swap।

मुख्य बातें

  1. start के बाईं तरफ़ सब कुछ पहले से sorted है; start से आगे का हिस्सा नहीं।
  2. minimum unsorted हिस्से में अब तक मिली सबसे छोटी वैल्यू का index याद रखता है।
  3. अंदर वाला लूप for index in range(start + 1, len(result)): बाकी लिस्ट देखता है।
  4. result[start], result[minimum] = result[minimum], result[start] हर जगह के लिए एक swap करता है।

इसका उपयोग कब करें?

  • Sorting के तरीके सीखना और उनकी तुलना करना।
  • ऐसी स्थितियाँ जहाँ आइटम लिखना या हिलाना महँगा है और तुलना सस्ती।
  • k passes के बाद रुककर k सबसे छोटे आइटम ढूँढना।

कब ज़रूरत नहीं

  • असली प्रोग्राम: sorted() कहीं ज़्यादा तेज़ है।
  • लगभग sorted डेटा: selection sort फिर भी सब कुछ देखता है, जबकि insertion sort जल्दी ख़त्म हो जाता है।

Python में Selection Sort Visualizer

O(n²)

हर comparison और data movement देखने के लिए चलाएँ या अगला चरण दबाएँ।

उदाहरण कोड

कोड चलाएँ →
main.py
def selection_sort(values):
    result = values.copy()
    for start in range(len(result)):
        minimum = start
        for index in range(start + 1, len(result)):
            if result[index] < result[minimum]:
                minimum = index
        result[start], result[minimum] = result[minimum], result[start]
    return result

print(selection_sort([64, 25, 12, 22, 11]))
इस उदाहरण के लिए Run बटन बनाएँ

अपेक्षित आउटपुट

[11, 12, 22, 25, 64]

यह कैसे काम करता है

हर pass minimum खोजता है: समय O(n²) और अतिरिक्त memory O(1) है।

मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।

अभ्यास के कार्य

बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।

  1. खाली input, एक element और duplicate values जाँचें।
  2. हर चरण के बाद state दिखाएँ।
  3. Performance को दूसरे solution से तुलना करें।
Python IDE में चलाएँ →

आम गलतियाँ

अंदर वाले लूप में swap करना

इससे यह कई swaps वाला धीमा और उलझा हुआ sort बन जाता है।

समस्या
for index in range(start + 1, len(result)):
    if result[index] < result[start]:
        result[start], result[index] = result[index], result[start]
सुधार
for index in range(start + 1, len(result)):
    if result[index] < result[minimum]:
        minimum = index
result[start], result[minimum] = result[minimum], result[start]

यह पाठ पूरा कर लिया?

अपनी प्रगति ट्रैक करने के लिए इसे सीखा हुआ मार्क करें।

चैलेंज से अभ्यास करें

इस पाठ में सीखी बात से एक असली समस्या हल करें। हर चैलेंज ब्राउज़र में चलता है, तुरंत टेस्ट और AI रिव्यू के साथ।

सभी चैलेंज