चयन सॉर्ट
चयन सॉर्ट एल्गोरिथ्म सबसे बुनियादी और सहज ज्ञान आधारित सॉर्टिंग एल्गोरिथ्म में से एक है। यह बार-बार सरणी (array) से न्यूनतम (minimum) तत्व ढूँढता है और उसे सबसे आगे ले आता है। इसके बाद शेष बचे हुए भाग से दोबारा न्यूनतम तत्व ढूँढने की प्रक्रिया दोहराई जाती है, और यह क्रम अंत तक चलता रहता है।
a = [...]
for i in range(len(a)): # हमें a[i:] का न्यूनतम तत्व a[i] पर रखना चाहिए
min_idx = i # न्यूनतम तत्व का इंडेक्स
for j in range(i + 1, len(a)): # न्यूनतम तत्व का इंडेक्स ढूँढ़ें
if a[j] < a[min_idx]: # अगर कोई छोटा तत्व मिले
min_idx = j # न्यूनतम तत्व का इंडेक्स अपडेट करें
a[i], a[min_idx] = a[min_idx], a[i] # a[i] और a[min_idx] को स्वैप करें
print(a)प्रत्येक दोहराव (iteration) में, हम बचे हुए भाग से न्यूनतम मान लेते हैं और वर्तमान तत्व तथा उस न्यूनतम तत्व को उनके इंडेक्स का उपयोग करके अदल-बदल (swap) कर देते हैं। अगर वर्तमान तत्व ही न्यूनतम है, तो मौजूदा तत्व उसी से स्वैप होगा, जिससे सरणी में कोई बदलाव नहीं होगा।
चयन सॉर्ट एल्गोरिथ्म सरणी में से न्यूनतम तत्व ढूँढकर उसे वर्तमान इंडेक्स से स्वैप करता है। इसका मतलब है कि प्रत्येक चरण में, हमें शेष सरणी के हर तत्व को जाँचना पड़ता है ताकि सही न्यूनतम मिल सके (क्योंकि
min फ़ंक्शन या इसी तरह की प्रक्रिया सरणी के प्रत्येक तत्व को जाँचती है)। इसी कारण पूरी अल्गोरिथ्म की समय जटिलता n चक्रों के आधार पर लगभग n पुनरावृत्तियों के बराबर होती है ⇒ कुल ऑपरेशनों में।आइए इसे कुछ सरणियों पर लागू करके देखें:
[4, 1, -1, 0, 2, 8]
- i = 0 ⇒ val = -1 ⇒ idx = 2 ⇒ swap ⇒ [-1, 1, 4, 0, 2, 8]
- i = 1 ⇒ val = 0 ⇒ idx = 3 ⇒ swap ⇒ [-1, 0, 4, 1, 2, 8]
- i = 2 ⇒ val = 1 ⇒ idx = 3 ⇒ swap ⇒ [-1, 0, 1, 4, 2, 8]
- i = 3 ⇒ val = 2 ⇒ idx = 4 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
- i = 4 ⇒ val = 4 ⇒ idx = 4 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
- i = 5 ⇒ val = 8 ⇒ idx = 5 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
[10, 5, 1, -1, -2, -7]
- i = 0 ⇒ val = -7 ⇒ idx = 5 ⇒ swap ⇒ [-7, 5, 1, -1, -2, 10]
- i = 1 ⇒ val = -2 ⇒ idx = 4 ⇒ swap ⇒ [-7, -2, 1, -1, 5, 10]
- i = 2 ⇒ val = -1 ⇒ idx = 3 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
- i = 3 ⇒ val = 1 ⇒ idx = 3 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
- i = 4 ⇒ val = 5 ⇒ idx = 4 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
- i = 5 ⇒ val = 10 ⇒ idx = 5 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
[1, 2, 3, 4, 5]
- i = 0 ⇒ val = 1 ⇒ idx = 0 ⇒ swap ⇒ [1, 2, 3, 4, 5]
- i = 1 ⇒ val = 2 ⇒ idx = 1 ⇒ swap ⇒ [1, 2, 3, 4, 5]
- i = 2 ⇒ val = 3 ⇒ idx = 2 ⇒ swap ⇒ [1, 2, 3, 4, 5]
- i = 3 ⇒ val = 4 ⇒ idx = 3 ⇒ swap ⇒ [1, 2, 3, 4, 5]
- i = 4 ⇒ val = 5 ⇒ idx = 4 ⇒ swap ⇒ [1, 2, 3, 4, 5]
चुनौती
दिए गए n पूर्णांकों को (integers) चयन सॉर्ट का उपयोग करते हुए आरोही क्रम में व्यवस्थित कीजिए।
इनपुट
इनपुट की पहली पंक्ति में एकमात्र पूर्णांक n (1 ≤ n ≤ 1000) होता है, जो सरणी में मौजूद तत्वों की संख्या बताता है।
अगली पंक्ति में n अंतराल से अलग किए गए पूर्णांक दिए जाते हैं: a1, a2, ... a_n (जिनकी मान-सीमा -10^9 से 10^9 के बीच है)।
आउटपुट
कार्यक्रम को इनपुट में दी गई सरणी को आरोही क्रम में छाँटकर प्रदर्शित करना चाहिए।
उदाहरण
Input | Output |
5
5 5 3 2 3 | 2 3 3 5 5 |
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB