सिलेक्शन सॉर्ट

सिलेक्शन सॉर्ट

Class	Sorting algorithm
Data structure	Array
Worst-case performance	$O(n^{2})$ comparisons, $O(n)$ swaps
Best-case performance	$O(n^{2})$ comparisons, $O(1)$ swap
Average performance	$O(n^{2})$ comparisons, $O(n)$ swaps
Worst-case space complexity	$O(1)$ auxiliary

कंप्यूटर विज्ञान में, चयन सॉर्ट एक इन-प्लेस तुलना सॉर्टिंग एल्गोरिदम है। इसमें O(n²) समय जटिलता है, जो इसे बड़ी सूचियों पर अक्षम बनाती है, और सामान्यतः समान प्रविष्टि प्रकार से भी खराब प्रदर्शन करती है। चयन सॉर्ट अपनी सादगी के लिए जाना जाता है और कुछ स्थितियों में अधिक जटिल एल्गोरिदम पर प्रदर्शन लाभ होता है, विशेषकर जहां सहायक मेमोरी सीमित होती है।

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

चयन प्रकार की समय दक्षता द्विघात है, इसलिए कई छँटाई विधियाँ हैं जिनमें चयन प्रकार की तुलना में उत्तम समय जटिलता है।

उदाहरण

यहां पांच तत्वों को क्रमबद्ध करने वाले इस सॉर्ट एल्गोरिदम का एक उदाहरण दिया गया है:

क्रमबद्ध उपसूची	अवर्गीकृत उपसूची	अवर्गीकृत सूची में सबसे कम तत्व
()	(11, 25, 12, 22, 64)	11
(11)	(25, 12, 22, 64)	12
(11, 12)	(25, 22, 64)	22
(11, 12, 22)	(25, 64)	25
(11, 12, 22, 25)	(64)	64
(11, 12, 22, 25, 64)	()

चयन सॉर्ट एनीमेशन. लाल वर्तमान मिनट है. पीली क्रमबद्ध सूची है. नीला वर्तमान वस्तु है.

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

arr[] = 64 25 12 22 11

// Find the minimum element in arr[0...4]
// and place it at beginning
11 25 12 22 64

// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
11 12 25 22 64

// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
11 12 22 25 64

// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
11 12 22 25 64

कार्यान्वयन

नीचे C (प्रोग्रामिंग भाषा) में एक कार्यान्वयन है।

/* a[0] to a[aLength-1] is the array to sort */
int i,j;
int aLength; // initialise to a's length

/* advance the position through the entire array */
/*   (could do i < aLength-1 because single element is also min element) */
for (i = 0; i < aLength-1; i++)
{
    /* find the min element in the unsorted a[i .. aLength-1] */

    /* assume the min is the first element */
    int jMin = i;
    /* test against elements after i to find the smallest */
    for (j = i+1; j < aLength; j++)
    {
        /* if this element is less, then it is the new minimum */
        if (a[j] < a[jMin])
        {
            /* found new minimum; remember its index */
            jMin = j;
        }
    }

    if (jMin != i) 
    {
        swap(a[i], a[jMin]);
    }
}

जटिलता

अन्य सॉर्टिंग एल्गोरिदम की तुलना में चयन सॉर्ट का विश्लेषण करना मुश्किल नहीं है, क्योंकि कोई भी लूप सरणी में डेटा पर निर्भर नहीं करता है। न्यूनतम का चयन करने के लिए स्कैनिंग की आवश्यकता होती है $n$ तत्व (लेना $n-1$ तुलनाएँ) और फिर इसे पहले स्थान पर स्वैप करना। अगले निम्नतम तत्व को खोजने के लिए शेष को स्कैन करने की आवश्यकता होती है $n-2$ तत्व वगैरह. इसलिए, तुलनाओं की कुल संख्या है

$(n-1)+(n-2)+...+1=\sum _{i=1}^{n-1}i$

अंकगणितीय प्रगति से,

$\sum _{i=1}^{n-1}i={\frac {(n-1)+1}{2}}(n-1)={\frac {1}{2}}n(n-1)={\frac {1}{2}}(n^{2}-n)$

जो जटिलता का है $O(n^{2})$ तुलनाओं की संख्या के संदर्भ में. इनमें से प्रत्येक स्कैन के लिए एक स्वैप की आवश्यकता होती है $n-1$ तत्व (अंतिम तत्व पहले से ही मौजूद है)।

अन्य सॉर्टिंग एल्गोरिदम की तुलना

द्विघात सॉर्टिंग एल्गोरिदम के बीच (बिग ओ नोटेशन के एक साधारण औसत-केस के साथ सॉर्टिंग एल्गोरिदम#बैचमन-लैंडौ नोटेशन का परिवार|Θ(n)²)), चयन सॉर्ट लगभग हमेशा बुलबुले की तरह और सूक्ति प्रकार से उत्तम प्रदर्शन करता है। सम्मिलन सॉर्ट बहुत समान है, के-वें पुनरावृत्ति के बाद, पहला $k$ सरणी में तत्व क्रमबद्ध क्रम में हैं। इंसर्शन सॉर्ट का लाभ यह है कि यह केवल उतने ही तत्वों को स्कैन करता है जितनी उसे रखने के लिए आवश्यकता होती है $k+1$सेंट तत्व, जबकि चयन सॉर्ट को खोजने के लिए सभी शेष तत्वों को स्कैन करना होगा $k+1$सेंट तत्व.

सरल गणना से पता चलता है कि प्रविष्टि सॉर्ट सामान्यतः चयन सॉर्ट की तुलना में लगभग आधी तुलनाएँ निष्पादित करेगा, हालाँकि सॉर्टिंग से पहले सरणी जिस क्रम में थी, उसके आधार पर यह उतनी ही या उससे भी कम तुलनाएँ निष्पादित कर सकता है। इसे कुछ वास्तविक-समय कंप्यूटिंग|वास्तविक-समय अनुप्रयोगों के लिए एक लाभ के रूप में देखा जा सकता है कि चयन सॉर्ट सरणी के क्रम की परवाह किए बिना समान रूप से प्रदर्शन करेगा, जबकि सम्मिलन सॉर्ट का चलने का समय काफी भिन्न हो सकता है। हालाँकि, यह अक्सर सम्मिलन सॉर्ट के लिए एक फायदा है क्योंकि यदि सरणी पहले से ही सॉर्ट की गई है या सॉर्ट के करीब है तो यह अधिक कुशलता से चलता है।

जबकि लेखन की संख्या के संदर्भ में चयन सॉर्ट सम्मिलन सॉर्ट से उत्तम है ($n-1$ स्वैप बनाम तक $n(n-1)/2$ स्वैप, प्रत्येक स्वैप दो राइट्स के साथ), यह चक्र सॉर्ट द्वारा प्राप्त सैद्धांतिक न्यूनतम से लगभग दोगुना है, जो अधिकतम एन राइट्स करता है। यह महत्वपूर्ण हो सकता है यदि लिखना पढ़ने की तुलना में काफी महंगा है, जैसे कि EEPROM या फ्लैश मेमोरी के साथ, जहां प्रत्येक लेखन मेमोरी के जीवनकाल को कम कर देता है।

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

अंत में, बड़े सरणियों पर चयन सॉर्ट का प्रदर्शन काफी उत्तम होता है $\Theta (n\log n)$ फूट डालो और जीतो एल्गोरिदम|बांटो और जीतो एल्गोरिदम जैसे मर्ज़ सॉर्ट हालाँकि, प्रविष्टि सॉर्ट या चयन सॉर्ट दोनों सामान्यतः छोटे सरणियों (यानी 10-20 से कम तत्वों) के लिए तेज़ होते हैं। पुनरावर्ती एल्गोरिदम के लिए अभ्यास में एक उपयोगी अनुकूलन छोटे पर्याप्त उपसूचियों के लिए सम्मिलन सॉर्ट या चयन सॉर्ट पर स्विच करना है।

वेरिएंट

ढेर बनाएं और छांटें सबसे कम डेटा को खोजने और हटाने में तेजी लाने के लिए एक [[अंतर्निहित डेटा संरचना]] हीप (डेटा संरचना) डेटा संरचना का उपयोग करके बुनियादी एल्गोरिदम में काफी सुधार करता है। यदि सही ढंग से कार्यान्वित किया जाता है, तो ढेर अगले निम्नतम तत्व को ढूंढने की अनुमति देगा $\Theta (\log n)$ के बजाय समय $\Theta (n)$ सामान्य चयन प्रकार में आंतरिक लूप के लिए, कुल चलने का समय कम हो जाता है $\Theta (n\log n)$.

चयन सॉर्ट का एक द्विदिश संस्करण (कॉकटेल शेकर सॉर्ट की समानता के कारण डबल चयन सॉर्ट या कभी-कभी कॉकटेल सॉर्ट कहा जाता है) प्रत्येक पास में सूची में दोनों न्यूनतम और अधिकतम मान पाता है। इसके लिए नियमित चयन प्रकार की प्रति आइटम एक तुलना के बजाय प्रति दो आइटमों में तीन तुलनाओं की आवश्यकता होती है (तत्वों की एक जोड़ी की तुलना की जाती है, फिर बड़े की तुलना अधिकतम से की जाती है और छोटे की तुलना न्यूनतम से की जाती है), लेकिन इसके लिए केवल आधे पास की आवश्यकता होती है, शुद्ध 25% की बचत।

चयन सॉर्ट को सॉर्टिंग एल्गोरिदम # वर्गीकरण के रूप में कार्यान्वित किया जा सकता है, यदि चरण 2 में स्वैप करने के बजाय, न्यूनतम मान को पहली स्थिति में डाला जाता है और हस्तक्षेप करने वाले मान ऊपर स्थानांतरित हो जाते हैं। हालाँकि, इस संशोधन के लिए या तो एक डेटा संरचना की आवश्यकता होती है जो कुशल सम्मिलन या विलोपन का समर्थन करती है, जैसे कि एक लिंक की गई सूची, या यह प्रदर्शन की ओर ले जाती है $\Theta (n^{2})$ लिखता है.

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

bingo(array A)

{ This procedure sorts in ascending order by
  repeatedly moving maximal items to the end. }
begin
    last := length(A) - 1;

    { The first iteration is written to look very similar to the subsequent ones,
      but without swaps. }
    nextMax := A[last];
    for i := last - 1 downto 0 do
        if A[i] > nextMax then
            nextMax := A[i];
    while (last > 0) and (A[last] = nextMax) do
        last := last - 1;

    while last > 0 do begin
        prevMax := nextMax;
        nextMax := A[last];
        for i := last - 1 downto 0 do
             if A[i] > nextMax then
                 if A[i] <> prevMax then
                     nextMax := A[i];
                 else begin
                     swap(A[i], A[last]);
                     last := last - 1;
                 end
        while (last > 0) and (A[last] = nextMax) do
            last := last - 1;
    end;
end;

इस प्रकार, यदि औसतन समान मूल्य वाले दो से अधिक आइटम हैं, तो बिंगो सॉर्ट के तेज़ होने की उम्मीद की जा सकती है क्योंकि यह चयन सॉर्ट की तुलना में आंतरिक लूप को कम बार निष्पादित करता है।

यह भी देखें

• चयन एल्गोरिथ्म

संदर्भ

• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison–Wesley, 1997. ISBN 0-201-89685-0. Pages 138–141 of Section 5.2.3: Sorting by Selection.
• Anany Levitin. Introduction to the Design & Analysis of Algorithms, 2nd Edition. ISBN 0-321-35828-7. Section 3.1: Selection Sort, pp 98–100.
• Robert Sedgewick. Algorithms in C++, Parts 1–4: Fundamentals, Data Structure, Sorting, Searching: Fundamentals, Data Structures, Sorting, Searching Pts. 1–4, Second Edition. Addison–Wesley Longman, 1998. ISBN 0-201-35088-2. Pages 273–274

बाहरी संबंध

• Animated Sorting Algorithms: Selection Sort at the Wayback Machine (archived 7 March 2015) – graphical demonstration