चयन एल्गोरिथ्म: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(14 intermediate revisions by 4 users not shown)
Line 2: Line 2:
{{for|अनुवांशिक एल्गोरिदम में कृत्रिम प्राकृतिक चयन|चयन (आनुवंशिक एल्गोरिथम)}}
{{for|अनुवांशिक एल्गोरिदम में कृत्रिम प्राकृतिक चयन|चयन (आनुवंशिक एल्गोरिथम)}}
{{more footnotes|date=जुलाई 2017}}
{{more footnotes|date=जुलाई 2017}}
[[ कंप्यूटर विज्ञान |'''''कंप्यूटर विज्ञान''''']] '''''में''''', एक चयन एल्गोरिदम की  [[सूची (सार डेटा प्रकार)|सूची]]  या सरणी में ''k''th सबसे छोटी संख्या खोजने के लिए एल्गोरिदम है। इस तरह की संख्या को kth  ''[[ order statistic |क्रम सांख्यिकी]]''  कहा जाता है। इसमें [[ न्यूनतम |न्यूनतम]], अधिकतम और माध्यमिक तत्वों को खोजने की परिस्थिति सम्मिलित होती हैं। O(''n'')-time (सबसे खराब स्थिति का रैखिक समय) अधिकतम एल्गोरिदम हैं, तथा संरचित डेटा के लिए उपरेखीय प्रदर्शन संभव होता है। अत्यन्त O(1) वर्गीकृत किए गए डेटा की एक सरणी के लिए, चयनित अधिक जटिल समस्याओं जैसे  [[निकटतम पड़ोसी समस्या|निकटतम पास की]]  और सबसे छोटी पथ समस्याओं की उप-समस्या है। कई चयनित एल्गोरिदम एक  [[ छँटाई एल्गोरिथ्म |वर्गीकरण एल्गोरिथ्म]]  को सामान्यीकृत करके व्युत्पन्न किए जाते हैं, और इसके विपरीत कुछ वर्गिकरण एल्गोरिदम चयन के बार-बार आवेदन के रूप में प्राप्त किए जा सकते हैं।
[[ कंप्यूटर विज्ञान |'''''कंप्यूटर विज्ञान''''']] ''में'', एक चयन एल्गोरिदम की  [[सूची (सार डेटा प्रकार)|सूची]]  या सारणी में kth सबसे छोटी संख्या खोजने के लिए एल्गोरिदम है। इस तरह की संख्या को kth  ''[[ order statistic |क्रम सांख्यिकी]]''  कहा जाता है। इसमें [[ न्यूनतम |न्यूनतम]], अधिकतम और माध्यमिक तत्वों को खोजने की परिस्थिति सम्मिलित होती हैं। O(''n'')-time (सबसे खराब स्थिति का रैखिक समय) अधिकतम एल्गोरिदम हैं, तथा संरचित डेटा के लिए उपरेखीय प्रदर्शन संभव होता है। अत्यन्त O(1) वर्गीकृत किए गए डेटा की एक सरणी के लिए, चयनित अधिक जटिल समस्याओं जैसे  [[निकटतम पड़ोसी समस्या|निकटतम पास की]]  और सबसे छोटी पथ समस्याओं की उप-समस्या है। कई चयनित एल्गोरिदम एक  [[ छँटाई एल्गोरिथ्म |वर्गीकरण एल्गोरिथ्म]]  को सामान्यीकृत करके व्युत्पन्न किए जाते हैं, और इसके विपरीत कुछ वर्गिकरण एल्गोरिदम चयन के बार-बार अनुप्रयोग के रूप में प्राप्त किए जा सकते हैं।


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


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


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


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


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


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


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


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


अधिक आम तौर पर, आंशिक चयन प्रकार एक साधारण चयन एल्गोरिदम उत्पन्न करता है जिसमें ओ (केएन) समय लगता है। यह स्पर्शोन्मुख रूप से अक्षम है, लेकिन यदि k छोटा है, और इसे लागू करना आसान है तो यह पर्याप्त रूप से कुशल हो सकता है। सीधे तौर पर, हम केवल न्यूनतम मान पाते हैं और इसे शुरुआत में ले जाते हैं, शेष सूची पर दोहराते हुए जब तक कि हमारे पास k तत्व जमा नहीं हो जाते हैं, और फिर kth तत्व वापस कर देते हैं। यहाँ आंशिक चयन सॉर्ट-आधारित एल्गोरिथम है:
अधिक सामान्य रूप से एक आंशिक चयन वर्गीकरण सरल चयन एल्गोरिदम उत्पन्न करता है, जो O(''kn'') time लेता है। यह असम्बद्ध रूप से अप्रभावी होता है, लेकिन पर्याप्त रूप से कुशल हो सकता है यदि k छोटा है, तथा लागू करना आसान है। विशेष रूप से हम केवल एसके न्यूनतम मान को पाते हैं और इसे प्रारम्भ में ले जाते हैं, शेष सूची में तब तक दोहराते हैं जब तक कि हम k तत्वों को संचित नहीं कर लेते हैं, और फिर kth तत्व को वापस कर देते हैं। यह आंशिक चयन वर्गीकरण-आधारित एल्गोरिथम मे होता है।
'''function''' select(list[1..n], k)
    '''for''' i '''from''' 1 '''to''' k
        minIndex = i
        minValue = list[i]
        '''for''' j '''from''' i+1 '''to''' n '''do'''
            '''if''' list[j] < minValue '''then'''
                minIndex = j
                minValue = list[j]
        swap list[i] and list[minIndex]
    '''return''' list[k]


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


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


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


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


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


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


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


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


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


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


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