Python में Selection Sort
हर चरण में सबसे छोटा बचा element सही स्थान पर रखें।
में 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] = ...🔄 सबसे छोटे को खाली जगह पर लाइएSelection sort बार-बार लिस्ट के unsorted हिस्से में सबसे छोटा आइटम ढूँढता है और उसे sorted हिस्से की अगली जगह पर swap कर देता है। इसमें O(n²) तुलनाएँ लगती हैं, लेकिन ज़्यादा से ज़्यादा n - 1 swap।
मुख्य बातें
startके बाईं तरफ़ सब कुछ पहले से sorted है;startसे आगे का हिस्सा नहीं।minimumunsorted हिस्से में अब तक मिली सबसे छोटी वैल्यू का index याद रखता है।- अंदर वाला लूप
for index in range(start + 1, len(result)):बाकी लिस्ट देखता है। 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 देखने के लिए चलाएँ या अगला चरण दबाएँ।
उदाहरण कोड
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]))
अपेक्षित आउटपुट
[11, 12, 22, 25, 64]
यह कैसे काम करता है
हर pass minimum खोजता है: समय O(n²) और अतिरिक्त memory O(1) है।
मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।
अभ्यास के कार्य
बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।
- खाली input, एक element और duplicate values जाँचें।
- हर चरण के बाद state दिखाएँ।
- Performance को दूसरे solution से तुलना करें।
आम गलतियाँ
अंदर वाले लूप में 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 रिव्यू के साथ।
- ऐरे न्यूनतम सूची में सबसे छोटा मान खोजें। आसान
- K-th Smallest Element Find the k-th smallest value without fully sorting. मध्यम