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

For अनुवांशिक एल्गोरिदम में कृत्रिम प्राकृतिक चयन, see चयन (आनुवंशिक एल्गोरिथम).

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

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

वर्गीकरण करके चयन

सूची या सरणी को क्रमबद्ध करके वांछित तत्व का चयन करके, चयन को क्रमबद्ध करने के लिए कम किया जा सकता है। यह विधि एकल तत्व का चयन करने के लिए अप्रभावी है, लेकिन कुशल है जब एक सरणी से कई चयन किए जाने की आवश्यकता होती है, तो इस स्थिति में केवल एक प्रारंभिक बहुमूल्य प्रकार की आवश्यकता होती है, जिसके बाद कई सुलभ चयन संचालन होते हैं। O(1) सरणी के लिए, हालांकि चयन एक लिंक की गई सूची में O(n) है, युग्म क्रमबद्ध यादृच्छिक पहुंच की कमी के कारण सामान्य रूप से वर्गीकरण के लिए O(n log n) time की आवश्यकता होती है, जहां n सूची की लंबाई है, हालांकि मूलांक वर्गीकरण और गिनती का प्रकार जैसे गैर-तुलनात्मक वर्गीकरण एल्गोरिदम के साथ निम्न परिबंध संभव है।

पूरी सूची या सरणी को क्रमबद्ध करने के अतिरिक्त k सबसे छोटे या k सबसे बड़े तत्वों का चयन करने के लिए आंशिक वर्गीकरण का उपयोग कर सकते हैं। kth सबसे छोटा (resp., kth सबसे बड़ा तत्व) तब आंशिक रूप से क्रमबद्ध सूची का सबसे बड़ा (resp., सबसे छोटा तत्व) होता है तो इसके बाद किसी सरणी में पहुँचने के लिए O(1) लगता है तथा किसी सूची में पहुँचने के लिए O(k) लेता है।

अनियंत्रित आंशिक वर्गीकरण

यदि आंशिक वर्गीकरण को तनाव मुक्त किया जाता है ताकि k सबसे छोटे तत्व वापस आ जाएँ, लेकिन क्रम में नहीं, O(k log k) के कारक को समाप्त किया जा सकता है। एक अतिरिक्त अधिकतम चयन (O(k) समय लेते हुए) आवश्यक है, लेकिन चूँकि $k\leq n$, यह अभी भी O(n) की स्पर्शोन्मुख जटिलता उत्पन्न करता है। वास्तव में, विभाजन-आधारित चयन एल्गोरिदम स्वयं kth सबसे छोटा तत्व और k सबसे छोटा तत्व (अन्य तत्वों के क्रम में नहीं) दोनों को उत्पन्न करता है। यह ओ (एन) समय में किया जा सकता है - त्वरित चयन की औसत जटिलता, और परिष्कृत विभाजन-आधारित चयन एल्गोरिदम की सबसे खराब स्थिति जटिलता।

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

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

आंशिक चयन प्रकार

आंशिक छँटाई द्वारा चयन का एक सरल उदाहरण आंशिक चयन प्रकार का उपयोग करना है।

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

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

'फ़ंक्शन' का चयन करें (सूची [1..n], k)
    'के लिए' मैं 'से' 1 'से' k
        मिनइंडेक्स = आई
        minValue = सूची [i]
        'के लिए' j 'से' i+1 'से' n 'do'
            'अगर' सूची [जे] <minValue 'तब'
                मिनइंडेक्स = जे
                minValue = सूची [जे]
        स्वैप सूची [i] और सूची [मिनइंडेक्स]
    'वापसी' सूची [के]

विभाजन-आधारित चयन

Further information: Quickselect

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

विभाजन-आधारित एल्गोरिदम आम तौर पर जगह में किया जाता है, जिसके परिणामस्वरूप डेटा को आंशिक रूप से सॉर्ट किया जाता है। O(n) अतिरिक्त स्थान की कीमत पर, मूल डेटा को बदले बिना, उन्हें जगह से बाहर किया जा सकता है।

=== पिवट रणनीति === के रूप में मेडियन चयन

Further information: Median of medians

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

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

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

चयन द्वारा वृद्धिशील छँटाई

छँटाई द्वारा चयन के विपरीत, बार-बार चयन द्वारा क्रमिक रूप से क्रमबद्ध किया जा सकता है। संक्षेप में, चयन केवल एक तत्व, kth तत्व उत्पन्न करता है। हालांकि, व्यावहारिक चयन एल्गोरिदम में अक्सर आंशिक छँटाई शामिल होती है, या ऐसा करने के लिए संशोधित किया जा सकता है। आंशिक छँटाई द्वारा चयन स्वाभाविक रूप से ऐसा करता है, तत्वों को k तक छाँटता है, और विभाजन द्वारा चयन भी कुछ तत्वों को छाँटता है: पिवोट्स को सही स्थिति में क्रमबद्ध किया जाता है, जिसमें kth तत्व अंतिम धुरी होता है, और पिवोट्स के बीच के तत्वों का मान होता है धुरी मूल्यों के बीच। विभाजन-आधारित चयन और विभाजन-आधारित छँटाई के बीच का अंतर, जैसा कि Quickselect बनाम Quicksort में है, यह है कि चयन में प्रत्येक धुरी के केवल एक तरफ रिकर्स करता है, केवल पिवोट्स को छांटता है (औसतन लॉग (एन) पिवोट्स का उपयोग किया जाता है), धुरी के दोनों किनारों पर पुनरावर्ती होने के बजाय।

इसका उपयोग उसी डेटा पर बाद के चयनों को गति देने के लिए किया जा सकता है; चरम में, एक पूरी तरह से क्रमबद्ध सरणी ओ (1) चयन की अनुमति देती है। इसके अलावा, पहले एक पूर्ण सॉर्ट करने की तुलना में, बार-बार चयन द्वारा क्रमिक रूप से सॉर्ट करना परिशोधन विश्लेषण कई चयनों पर सॉर्टिंग लागत।

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

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

== उपरेखीय समय == में चयन करने के लिए डेटा संरचनाओं का उपयोग करना डेटा की एक असंगठित सूची को देखते हुए, न्यूनतम तत्व को खोजने के लिए रैखिक समय (Ω(n)) की आवश्यकता होती है, क्योंकि हमें प्रत्येक तत्व की जांच करनी होती है (अन्यथा, हम इसे याद कर सकते हैं)। यदि हम सूची को व्यवस्थित करते हैं, उदाहरण के लिए इसे हर समय क्रमबद्ध करके रखते हैं, तो kth सबसे बड़ा तत्व का चयन करना तुच्छ है, लेकिन फिर सम्मिलन के लिए रैखिक समय की आवश्यकता होती है, जैसा कि दो सूचियों के संयोजन जैसे अन्य कार्यों में होता है।

उपरैखिक समय में एक आदेश आंकड़े खोजने की रणनीति उपयुक्त डेटा संरचनाओं का उपयोग करके डेटा को एक संगठित फैशन में संग्रहित करना है जो चयन की सुविधा प्रदान करता है। ऐसी दो डेटा संरचनाएँ ट्री-आधारित संरचनाएँ और फ़्रीक्वेंसी टेबल हैं।

जब केवल न्यूनतम (या अधिकतम) की आवश्यकता होती है, तो हीप (डेटा संरचना) का उपयोग करने के लिए एक अच्छा तरीका है, जो निरंतर समय में न्यूनतम (या अधिकतम) तत्व खोजने में सक्षम है, जबकि सम्मिलन सहित अन्य सभी ऑपरेशन ओ हैं (लॉग एन) या बेहतर। अधिक आम तौर पर, एक स्व-संतुलन बाइनरी सर्च ट्री को आसानी से संवर्धित किया जा सकता है ताकि एक तत्व को सम्मिलित करना और O(log n) समय में kth सबसे बड़ा तत्व खोजना संभव हो सके; इसे ऑर्डर स्टेटिस्टिक ट्री कहा जाता है। हम बस प्रत्येक नोड में कितने वंशज हैं, इसकी गिनती करते हैं, और इसका उपयोग यह निर्धारित करने के लिए करते हैं कि किस पथ का अनुसरण करना है। सूचना को कुशलता से अपडेट किया जा सकता है क्योंकि एक नोड को जोड़ने से केवल इसके ओ (लॉग एन) पूर्वजों की संख्या प्रभावित होती है, और पेड़ के घुमाव केवल रोटेशन में शामिल नोड्स की गिनती को प्रभावित करते हैं।

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

यदि हम लगभग sqrt(n) आकार का h चुनते हैं, और इनपुट समान रूप से वितरित होने के करीब है, तो यह योजना अपेक्षित O(sqrt(n)) समय में चयन कर सकती है। दुर्भाग्य से, यह रणनीति एक संकीर्ण अंतराल में तत्वों के क्लस्टरिंग के प्रति भी संवेदनशील है, जिसके परिणामस्वरूप बड़ी संख्या में तत्व हो सकते हैं (क्लस्टरिंग को एक अच्छे हैश फ़ंक्शन के माध्यम से समाप्त किया जा सकता है, लेकिन kth सबसे बड़े हैश मान वाले तत्व को खोजना नहीं है) बहुत उपयोगी)। इसके अतिरिक्त, हैश तालिकाओं की तरह इस संरचना को दक्षता बनाए रखने के लिए तालिका आकार बदलने की आवश्यकता होती है क्योंकि तत्व जोड़े जाते हैं और n h से बहुत बड़ा हो जाता है^{2</उप>। इसका एक उपयोगी मामला डेटा की एक परिमित सीमा में ऑर्डर स्टेटिस्टिक या एक्सट्रीमम ढूंढ रहा है। बकेट अंतराल 1 के साथ उपरोक्त तालिका का उपयोग करना और प्रत्येक बकेट में गिनती बनाए रखना अन्य तरीकों से बहुत बेहतर है। ऐसी हैश तालिकाएँ वर्णनात्मक आँकड़ों में डेटा को वर्गीकृत करने के लिए उपयोग की जाने वाली आवृत्ति तालिकाओं की तरह होती हैं।}

निचली सीमा

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

अन्य इंडेक्स के लिए कहानी और अधिक जटिल हो जाती है। हम परिभाषित करते हैं $W_{t}(n)$ t सबसे छोटे मानों को खोजने के लिए आवश्यक तुलनाओं की न्यूनतम संख्या के रूप में। नुथ एस.एस. किसलिट्सिन द्वारा प्रकाशित एक पेपर का संदर्भ देता है, जो इस मूल्य पर एक ऊपरी सीमा दिखाता है:

$W_t(n)\le <!--\; \le \; -->n-<!--\; -\; -->t+\underset{}{\sum <!--\; \sum \; -->}$