चयन क्रम का उपयोग कैसे करें

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

एल्गोरिथम बार-बार ऐसा करता है जब तक कि सूची को क्रमबद्ध न किया जाए। यदि आप सुनिश्चित नहीं हैं कि चयन क्रम कैसे काम करता है, तो आप सही जगह पर आए हैं। हम आपको एक उदाहरण दिखाने के साथ-साथ इसे नीचे और अधिक गहराई से समझाएंगे।

चयन क्रम: एक नज़दीकी नज़र

मान लीजिए आपके पास सूची है: [३९, ८२, २, ५१, ३०, ४२, ७]। चयन क्रम का उपयोग करके सूची को क्रमबद्ध करने के लिए, आपको सबसे पहले इसमें सबसे बड़ी संख्या ढूंढनी होगी।

दी गई सूची के साथ, वह संख्या 82 है। उच्चतम सूचकांक (यानी, 7) में संख्या के साथ 82 स्वैप करें।

प्रथम पास के बाद सूची का नया क्रम होगा: [39, 7, 2, 51, 30, 42, 82]। हर बार एल्गोरिथ्म पूरी सूची से गुजरता है, जिसे "पास" कहा जाता है।

ध्यान दें कि सूची छँटाई प्रक्रिया के दौरान एक क्रमबद्ध उप-सूची और एक क्रमबद्ध उप-सूची को बनाए रखती है।

संबंधित: बिग-ओ नोटेशन क्या है?

मूल सूची शून्य वस्तुओं की एक क्रमबद्ध सूची और सभी वस्तुओं की एक क्रमबद्ध सूची से शुरू होती है। फिर पहले पास के बाद, इसकी एक क्रमबद्ध सूची होती है जिसमें केवल 82 नंबर होता है।

दूसरे पास पर, अनसॉर्टेड सबलिस्ट में सबसे ज्यादा संख्या 51 होगी। नीचे दी गई नई सूची आदेश देने के लिए इस नंबर को 42 से बदला जाएगा:

[39, 7, 2, 42, 30, 51, 82].

प्रक्रिया तब तक दोहराई जाती है जब तक कि पूरी सूची क्रमबद्ध न हो जाए। नीचे दिया गया आंकड़ा पूरी प्रक्रिया को सारांशित करता है:

बोल्ड ब्लैक में नंबर उस समय उच्चतम सूची मान दिखाते हैं। हरे रंग में वे क्रमबद्ध सबलिस्ट दिखाते हैं।

एल्गोरिथम विश्लेषण

इस एल्गोरिथम की जटिलता (बिग-ओ नोटेशन का उपयोग करके) प्राप्त करने के लिए, नीचे का अनुसरण करें:

पहले पास पर, (n-1) तुलना की जाती है। दूसरे पास पर, (n-2)। तीसरे पास पर, (n-3) और इसी तरह (n-1)वीं पास तक, जो केवल एक तुलना करता है।

नीचे दी गई तुलनाओं को संक्षेप में प्रस्तुत करता है:

(n-1)+ (n-1)+ (n-1)+...+1 = ((n-1)n)/2.

इसलिए चयन क्रम O(n .) है²).

कोड कार्यान्वयन

कोड उन कार्यों को दिखाता है जिनका उपयोग आप पायथन और जावा का उपयोग करके चयन सॉर्ट करने के लिए कर सकते हैं।

अजगर:

def चयनसॉर्ट (mylist):
रेंज में x के लिए (लेन (mylist) - 1, 0, -1):
मैक्स_आईडीएक्स = 0
श्रेणी में स्थिति के लिए (1, x + 1):
अगर mylist[posn] > mylist[max_idx]:
max_idx = posn
अस्थायी = मेरी सूची [एक्स]
mylist[x] = mylist[max_idx]
mylist[max_idx] = अस्थायी

जावा:

शून्य चयनसॉर्ट (int my_array[]){ 
के लिए (इंट एक्स = 0; एक्स < my_array.length - 1; एक्स++) 
{ 
इंट इंडेक्स = एक्स; 
के लिए (इंट वाई = एक्स + 1; वाई < my_array.length; वाई++){ 
अगर (my_array[y] सूचकांक = वाई; // सबसे कम सूचकांक खोजें 
} 
} 
int अस्थायी = my_array [सूचकांक]; // अस्थायी एक अस्थायी भंडारण है
my_array [सूचकांक] = my_array [x]; 
my_array [x] = अस्थायी; 
}}

सिलेक्शन सॉर्ट से मर्ज सॉर्ट की ओर बढ़ते हुए

जैसा कि ऊपर दिए गए एल्गोरिथम विश्लेषण ने दिखाया है, चयन सॉर्ट एल्गोरिथ्म O(n .) है²). इसकी एक घातीय जटिलता है और इसलिए यह बहुत बड़े डेटा सेट के लिए अक्षम है।

उपयोग करने के लिए एक बेहतर एल्गोरिदम ओ (nlogn) की जटिलता के साथ मर्ज सॉर्ट होगा। और अब आप जानते हैं कि चयन क्रम कैसे काम करता है, एल्गोरिदम को सॉर्ट करने के लिए आपकी अध्ययन सूची में अगला मर्ज सॉर्ट होना चाहिए।

लेखक के बारे में