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

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

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$ तत्व क्रमबद्ध क्रम में होते हैं। इंसर्शन सॉर्ट का लाभ यह है कि यह केवल उतने ही तत्वों को स्कैन करता है जितनी उसे $k+1$ सेंट तत्व को रखने के लिए आवश्यकता होती है, जबकि सिलेक्शन सॉर्ट को $k+1$ सेंट तत्व को खोजने के लिए सभी शेष तत्वों को स्कैन करना होगा।

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

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

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

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

प्रकार

हीपसॉर्ट सबसे कम डेटा को खोजने और हटाने में तेजी लाने के लिए एक अंतर्निहित डेटा संरचना हीप (डेटा संरचना) डेटा संरचना का उपयोग करके मूल एल्गोरिदम में अधिक सुधार करता है। यदि सही विधि से कार्यान्वित किया जाता है, तो हीप सामान्य सिलेक्शन प्रकार में आंतरिक लूप के लिए $\Theta (n)$ के अतिरिक्त $\Theta (\log 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