सिलेक्शन सॉर्ट: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(9 intermediate revisions by 4 users not shown)
Line 12: Line 12:
}}
}}


[[कंप्यूटर विज्ञान]] में, चयन सॉर्ट एक [[इन-प्लेस एल्गोरिदम|इन-प्लेस तुलना]]  [[छँटाई एल्गोरिथ्म|सॉर्टिंग एल्गोरिदम]] है। इसमें [[ बिग ओ अंकन |O(n<sup>2</sup>)]] समय जटिलता है, जो इसे बड़ी सूचियों पर अक्षम बनाती है, और सामान्यतः समान प्रविष्टि प्रकार से भी खराब प्रदर्शन करती है। चयन सॉर्ट अपनी सादगी के लिए जाना जाता है और कुछ स्थितियों में अधिक जटिल एल्गोरिदम पर प्रदर्शन लाभ होता है, विशेषकर जहां सहायक मेमोरी सीमित होती है।
[[कंप्यूटर विज्ञान]] में, '''सिलेक्शन सॉर्ट''' एक [[इन-प्लेस एल्गोरिदम|इन-प्लेस तुलना]]  [[छँटाई एल्गोरिथ्म|सॉर्टिंग एल्गोरिदम]] है। इसमें [[ बिग ओ अंकन |O(n<sup>2</sup>)]] समय जटिलता है, जो इसे बड़ी सूचियों पर अक्षम बनाती है, और सामान्यतः समान प्रविष्टि प्रकार से भी खराब प्रदर्शन करती है। सिलेक्शन सॉर्ट अपनी सादगी के लिए जाना जाता है और कुछ स्थितियों में अधिक जटिल एल्गोरिदम पर प्रदर्शन लाभ होता है, विशेषकर जहां सहायक मेमोरी सीमित होती है।


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


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


== उदाहरण ==
== उदाहरण ==
Line 50: Line 50:
|
|
|}
|}
[[Image:Selection-Sort-Animation.gif|right|thumb|चयन सॉर्ट एनीमेशन. लाल वर्तमान मिनट है. पीली क्रमबद्ध सूची है. नीला वर्तमान वस्तु है.]](इन अंतिम दो पंक्तियों में कुछ भी बदलाव नहीं हुआ है क्योंकि अंतिम दो संख्याएँ पहले से ही क्रम में थीं।)
[[Image:Selection-Sort-Animation.gif|right|thumb|सिलेक्शन सॉर्ट एनीमेशन. लाल वर्तमान मिनट है. पीली क्रमबद्ध सूची है. नीला वर्तमान वस्तु है.]](इन अंतिम दो पंक्तियों में कुछ भी बदलाव नहीं हुआ है क्योंकि अंतिम दो संख्याएँ पहले से ही क्रम में थीं।)


चयन सॉर्ट का उपयोग सूची संरचनाओं पर भी किया जा सकता है जो लिंक की गई सूची जैसे जोड़ने और हटाने को कुशल बनाते हैं। इस स्थिति में सूची के शेष भाग से न्यूनतम तत्व को हटाना और फिर इसे अब तक क्रमबद्ध मानों के अंत में सम्मिलित करना अधिक सामान्य है। उदाहरण के लिए:
सिलेक्शन सॉर्ट का उपयोग सूची संरचनाओं पर भी किया जा सकता है जो लिंक की गई सूची जैसे जोड़ने और हटाने को कुशल बनाते हैं। इस स्थिति में सूची के शेष भाग से न्यूनतम तत्व को हटाना और फिर इसे अब तक क्रमबद्ध मानों के अंत में सम्मिलित करना अधिक सामान्य है। उदाहरण के लिए:<syntaxhighlight lang="d">
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
</syntaxhighlight>


== कार्यान्वयन ==
== कार्यान्वयन ==
नीचे C (प्रोग्रामिंग भाषा) में एक कार्यान्वयन है।
नीचे C (प्रोग्रामिंग भाषा) में एक कार्यान्वयन है।<syntaxhighlight lang="d" line="1">
<सिंटैक्सहाइलाइट लैंग= सी स्टाइल= ओवरफ्लो:ऑटो; चौड़ाई:ऑटो; पंक्ति = 1 >
/* a[0] to a[aLength-1] is the array to sort */
/* a[0] से a[aLength-1] सॉर्ट करने के लिए सरणी है */
int i,j;
int i,j;
int aLength; // a की लंबाई से प्रारंभ करें
int aLength; // initialise to a's length


/* संपूर्ण सरणी में स्थिति को आगे बढ़ाएं */
/* advance the position through the entire array */
/* (मैं < aLength-1 कर सकता हूं क्योंकि एकल तत्व भी न्यूनतम तत्व है) */
/*   (could do i < aLength-1 because single element is also min element) */
(i = 0; i < aLength-1; i++) के लिए
for (i = 0; i < aLength-1; i++)
{
{
  /* अवर्गीकृत a[i .. aLength-1] में न्यूनतम तत्व ढूंढें */
    /* find the min element in the unsorted a[i .. aLength-1] */


  /* मान लें कि न्यूनतम पहला तत्व है */
    /* assume the min is the first element */
  int jMin = i;
    int jMin = i;
  /* सबसे छोटे को खोजने के लिए i के बाद तत्वों के विरुद्ध परीक्षण करें */
    /* test against elements after i to find the smallest */
  (j = i+1; j < aLength; j++) के लिए
    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;
  }
        }
  }
    }


  यदि (jMin != i)
    if (jMin != i)  
  {
    {
  स्वैप([आई], [जेमिन]);
        swap(a[i], a[jMin]);
  }
    }
}
}
</सिंटैक्सहाइलाइट>
</syntaxhighlight>


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


: <math>(n-1)+(n-2)+...+1 =
: <math>(n-1)+(n-2)+...+1 =
Line 98: Line 115:
\frac{1}{2}n(n-1)=
\frac{1}{2}n(n-1)=
\frac{1}{2}(n^2-n)</math>
\frac{1}{2}(n^2-n)</math>
जो जटिलता का है <math>O(n^2)</math> तुलनाओं की संख्या के संदर्भ में. इनमें से प्रत्येक स्कैन के लिए एक स्वैप की आवश्यकता होती है <math>n-1</math> तत्व (अंतिम तत्व पहले से ही मौजूद है)
जो तुलनाओं की संख्या के संदर्भ में जटिलता <math>O(n^2)</math> का है। इनमें से प्रत्येक स्कैन के लिए <math>n-1</math> तत्वों (अंतिम तत्व पहले से ही उपस्थित है) के लिए एक स्वैप की आवश्यकता होती है।


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


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


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


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


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


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


== वेरिएंट ==
== प्रकार ==


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


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


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


बिंगो सॉर्ट संस्करण में, सबसे बड़े मूल्य को खोजने के लिए शेष वस्तुओं को बार-बार देखकर और उस मूल्य के साथ ''सभी'' वस्तुओं को उनके अंतिम स्थान पर ले जाकर वस्तुओं को क्रमबद्ध किया जाता है।<ref>{{DADS|Bingo sort|bingosort}}</ref> गिनती सॉर्ट की तरह, यदि कई डुप्लिकेट मान हैं तो यह एक कुशल संस्करण है: चयन सॉर्ट प्रत्येक स्थानांतरित आइटम के लिए शेष आइटम के माध्यम से एक पास करता है, जबकि बिंगो सॉर्ट प्रत्येक मान के लिए एक पास करता है। सबसे बड़े मूल्य को खोजने के लिए प्रारंभिक पास के बाद, बाद के पास प्रत्येक आइटम को उस मूल्य के साथ उसके अंतिम स्थान पर ले जाते हैं, जबकि अगले मान को निम्नलिखित [[छद्मकोड]] में खोजते हैं (सरणी शून्य-आधारित होती है और फॉर-लूप में ऊपर और नीचे दोनों सीमाएं शामिल होती हैं) , जैसे [[पास्कल (प्रोग्रामिंग भाषा)]] में):
बिंगो सॉर्ट संस्करण में, सबसे बड़े मूल्य को खोजने के लिए शेष वस्तुओं को बार-बार देखकर और उस मूल्य के साथ ''सभी'' वस्तुओं को उनके अंतिम स्थान पर ले जाकर वस्तुओं को क्रमबद्ध किया जाता है।<ref>{{DADS|Bingo sort|bingosort}}</ref> गिनती सॉर्ट की तरह, यदि कई डुप्लिकेट मान हैं तो यह एक कुशल संस्करण है: सिलेक्शन सॉर्ट प्रत्येक स्थानांतरित आइटम के लिए शेष आइटम के माध्यम से एक पास करता है, जबकि बिंगो सॉर्ट प्रत्येक मान के लिए एक पास करता है। सबसे बड़े मूल्य को खोजने के लिए प्रारंभिक पास के बाद, बाद के पास प्रत्येक आइटम को उस मूल्य के साथ उसके अंतिम स्थान पर ले जाते हैं, जबकि अगले मान को निम्नलिखित [[छद्मकोड]] (सरणियाँ शून्य-आधारित हैं और फ़ॉर-लूप में [[पास्कल (प्रोग्रामिंग भाषा)]] की तरह ऊपर और नीचे दोनों सीमाएँ सम्मिलित हैं) में खोजते हैं:


<syntaxhighlight lang="pascal">
<syntaxhighlight lang="pascal">
Line 155: Line 172:
end;
end;
</syntaxhighlight>
</syntaxhighlight>
इस प्रकार, यदि औसतन समान मूल्य वाले दो से अधिक आइटम हैं, तो बिंगो सॉर्ट के तेज़ होने की उम्मीद की जा सकती है क्योंकि यह चयन सॉर्ट की तुलना में आंतरिक लूप को कम बार निष्पादित करता है।
इस प्रकार, यदि औसतन समान मान वाले दो से अधिक आइटम हैं, तो बिंगो सॉर्ट के तेज़ होने की अपेक्षा की जा सकती है क्योंकि यह सिलेक्शन सॉर्ट की तुलना में आंतरिक लूप को कम बार निष्पादित करता है।






== यह भी देखें ==
== यह भी देखें ==
* [[चयन एल्गोरिथ्म]]
* [[चयन एल्गोरिथ्म|सिलेक्शन एल्गोरिथ्म]]


== संदर्भ ==
== संदर्भ ==
Line 176: Line 193:


{{sorting}}
{{sorting}}
[[Category: छँटाई एल्गोरिदम]] [[Category: तुलना प्रकार]] [[Category: उदाहरण सी कोड वाले लेख]]


[[Category: Machine Translated Page]]
[[Category:Collapse templates]]
[[Category:Created On 10/07/2023]]
[[Category:Created On 10/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:Webarchive template wayback links]]
[[Category:Wikipedia metatemplates]]
[[Category:उदाहरण सी कोड वाले लेख]]
[[Category:छँटाई एल्गोरिदम]]
[[Category:तुलना प्रकार]]

Latest revision as of 17:31, 29 July 2023

सिलेक्शन सॉर्ट
ClassSorting algorithm
Data structureArray
Worst-case performance comparisons, swaps
Best-case performance comparisons, swap
Average performance comparisons, swaps
Worst-case space complexity auxiliary

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

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

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

उदाहरण

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

क्रमबद्ध उपसूची अवर्गीकृत उपसूची अवर्गीकृत सूची में सबसे कम तत्व
() (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)2 के एक साधारण औसत-मामले के साथ एल्गोरिदम को सॉर्ट करना) के बीच, सिलेक्शन सॉर्ट लगभग सदैव बबल सॉर्ट और गनोम सॉर्ट से उत्तम प्रदर्शन करता है। प्रविष्टि सॉर्ट बहुत समान है, जिसमे K-वें पुनरावृत्ति के बाद, सरणी में पहले तत्व क्रमबद्ध क्रम में होते हैं। इंसर्शन सॉर्ट का लाभ यह है कि यह केवल उतने ही तत्वों को स्कैन करता है जितनी उसे सेंट तत्व को रखने के लिए आवश्यकता होती है, जबकि सिलेक्शन सॉर्ट को सेंट तत्व को खोजने के लिए सभी शेष तत्वों को स्कैन करना होगा।

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

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

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

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

प्रकार

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

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

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

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

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;

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


यह भी देखें

संदर्भ

  1. Public Domain This article incorporates public domain material from Black, Paul E. "Bingo sort". Dictionary of Algorithms and Data Structures.
  • 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


बाहरी संबंध