चयन छांटना

चयन छांटना

चयन सॉर्ट एक प्रकार का एल्गोरिथ्म है। एक सॉर्टिंग एल्गोरिथ्म एक विशिष्ट क्रम में बड़ी संख्या में वस्तुओं को पुनर्गठित करने के लिए एक विधि है, जैसे कि वर्णानुक्रम, बढ़ते क्रम में या फिर घटते क्रम में। सॉर्टिंग एल्गोरिदम एक अरे मैं  अंको की सूची लेते हैं, उन सूचियों पर विशिष्ट संचालन करते हैं और आउटपुट के रूप में  क्रम में किए गए सरणियों को वितरित करते हैं।

चयन सॉर्ट एक सरल सॉर्टिंग एल्गोरिथ्म है। यह सॉर्टिंग एल्गोरिथ्म एक इन-प्लेस तुलना-आधारित एल्गोरिथ्म है। इसमें <math>\Theta(n^2)</math> समय की जटिलता है, जो इसे बड़ी सूचियों में अक्षम बनाता है। चयन प्रकार अपनी सादगी के लिए जाना जाता है और कुछ स्थितियों में अधिक जटिल एल्गोरिदम पर प्रदर्शन लाभ होता है, विशेष रूप से जहां सहायक मेमोरी सीमित है।

प्रक्रिया

एल्गोरिथम दी गई सूची को दो भागों में विभाजित करता है:  एक भाग मैं क्रम में जमाई गई सूची रखी जाती है यह सूची का पहला भाग होता है दूसरे भाग में क्रम का होना जरूरी नहीं। प्रारंभ में, क्रम में  किया गया सबलिस्ट खाली है और  दूसरे भाग में उसी क्रम में दी हुई सूची है। एल्गोरिथ्म सबसे छोटा (या सबसे बड़ा, सॉर्टिंग ऑर्डर पर निर्भर करता है) तत्व को अनसुलझी किए गए सबलिस्ट में तत्व के आधार पर प्राप्त करता है, इसे बाईं ओर के सबसे अनसोल्ड  तत्व ( दूसरे भाग का पहला अंक) से एक्सचेंज करता है, और सबलिस्ट को एक तत्व को दाईं ओर ले जाता है।

सबसे छोटे तत्व को अनरिस्टर्ड एरे से चुना जाता है और सबसे लेफ्ट एलिमेंट से बदल दिया जाता है, और वह एलिमेंट सॉर्ट किए गए एरे का एक हिस्सा बन जाता है। यह प्रक्रिया एक तत्व द्वारा दाईं ओर अनसोल्ड सरणी बाउंड्री चलती रहती है।

उदाहरण

चयन सॉर्ट

पहला भाग	दूसरा भाग	शीर्ष पाठ
()	(4,5,3,1,2)	1
(1)	(4,5,3,2)	2
(1,2)	(4,5,3)	3
(1,2,3)	(4,5)	4
(1,2,3,4)	(5)	5
(1,2,3,4,5)	()	null

कार्यान्वयन

नीचे C++ में एक कार्यान्वयन है

// Function takes two input one is  array and its size and sort it.
void selection_sort(int * arr , int n)
{
    for(int i=0;i<n;i++)
    {
        int ind=i;
        //Finding minimum element from right part of array
        for(int itr=i;itr<n;i++)
        {
            if(arr[ind]>arr[i])
                ind=itr;
        }
        //Swapping with minimum element 
        swap(arr[ind],arr[i]);
        
    }
}

जटिलता

न्यूनतम तत्व का चयन करने के लिए सभी n तत्वों को स्कैन करने की आवश्यकता होती है (यह n - 1 तुलना करता है) और फिर इसे पहली स्थिति में स्वैप करना। अगले न्यूनतम तत्व को खोजने के लिए शेष n - 1 तत्वों और इतने पर स्कैनिंग की आवश्यकता होती है,

<math>(n-1)+(n-2)+(n-3)+...+2+1 = \textstyle \sum_{k=1}^N \displaystyle k </math>

अंकगणितीय प्रगति के द्वारा,

<math>\textstyle \sum_{k=1}^n \displaystyle k = n (n-1) \div 2 </math>

<math>\Theta(n^2)</math>

सर्वोत्तम मामला: <math>\Theta(n^2)</math>

सबसे खराब स्थिति: <math>\Theta(n^2)</math>

औसत मामला: <math>\Theta(n^2)</math>

मेमोरी जटिलता: O (1)

स्थिर: नहीं