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

Latest revision as of 09:45, 25 November 2022

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

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

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

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

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

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

अधिक सामान्य रूप से एक आंशिक चयन वर्गीकरण सरल चयन एल्गोरिदम उत्पन्न करता है, जो 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]

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

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

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

महत्वपूर्ण योजना के रूप में मध्यस्थ चयन

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

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

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

चयन द्वारा वृद्धिशील वर्गीकरण

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

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

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

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

उप-रेखीय समय में चयन करने के लिए डेटा संरचनाओं का उपयोग करना

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

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

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

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

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

निचली सीमा

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

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

W_{t}(n)\leq n-t+\sum _{n+1-t<j\leq n}\lceil {\log _{2}\,j}\rceil \quad {\text{for}}\,n\geq t

यह बाउंड t=2 के लिए प्राप्त करने योग्य है लेकिन बेहतर, अधिक जटिल बाउंड बड़े t के लिए जाने जाते हैं।^{[citation needed]}

अंतरिक्ष जटिलता

चयन की आवश्यक स्थान जटिलता O(1) अतिरिक्त भंडारण है, जिसमें उस सरणी को संग्रहीत करने के अतिरिक्त जिसमें चयन किया जा रहा है। सर्वोत्तम O(n) समय जटिलता को बनाए रखते हुए ऐसी अंतरिक्ष जटिलता प्राप्त की जा सकती है।^[1]

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

ऑनलाइन एल्गोरिदम एक धारा के kth सबसे छोटे तत्व की गणना करने के लिए संकीर्ण रूप से संदर्भित हो सकता है, इस स्थिति में आंशिक वर्गीकृत एल्गोरिदम - k + O (1) के साथ k सबसे छोटे तत्वों के लिए अब तक का उपयोग किया जा सकता है, लेकिन विभाजन-आधारित एल्गोरिदम नहीं हो सकता है।

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

सबसे सरल उदाहरण उच्च संभावना के साथ अधिकतम चुनने की सचिव समस्या है, इस स्थिति में सर्वोत्तम योजना यादृच्छिक डेटा पर पहले n/e तत्वों के चल रहे अधिकतम को ट्रैक करना और उन्हें अस्वीकार करना है, और फिर पहले तत्व का अधिकतम से अधिक चयन करना है।

भाषा समर्थन

सामान्य चयन के लिए बहुत कम भाषाओं में अंतर्निहित समर्थन है, हालांकि कई सूची के सबसे छोटे या सबसे बड़े तत्व को खोजने की सुविधा प्रदान करते हैं। एक उल्लेखनीय अपवाद C++ है, जो अपेक्षित रैखिक समय की गारंटी के साथ एक टेम्प्लेटेड nth_element विधि प्रदान करता है, और डेटा को विभाजित भी करता है, जिसके लिए आवश्यक है कि nth तत्व को उसके सही स्थान पर क्रमबद्ध किया जाए, nth तत्व से पहले के तत्व इससे कम हैं, और तत्व nवें तत्व के बाद इससे अधिक हैं। यह निहित है लेकिन आवश्यक नहीं होता है, कि यह अपेक्षित रैखिक समय और डेटा के विभाजन की अपनी आवश्यकता के अनुसार होरे के एल्गोरिथ्म या कुछ संस्करण पर आधारित है।^[2]^[3]

पर्ल के लिए, सीपीएएन से उपलब्ध प्रारूप Sort::Key::Top, कई ऑर्डरिंग और कस्टम कुंजी निष्कर्षण प्रक्रियाओं का उपयोग करके सूची से शीर्ष एन तत्वों का चयन करने के लिए कार्यों का एक समुच्चय प्रदान करता है। इसके अतिरिक्त, सांख्यिकी::CaseResampling मॉड्यूल शीघ्र चयन का उपयोग करके विभाजक की गणना करने के लिए एक फलन प्रदान करता है।

पायथन (प्रोग्रामिंग भाषा) के मानक पुस्तकालय (2.4 के बाद से) में heapq.nsmallest() तथा nlargest() सम्मिलित हैं, जो O(n log k) समय में वर्गीकृत की गई सूचियों को लौटाते हैं।^[4] Numpy में partition() फलन है।

मैटलैब में maxk() और mink() फ़ंक्शन सम्मिलित हैं, जो सदिश के साथ-साथ उनके सूचकांकों में अधिकतम (न्यूनतम) k मान लौटाते हैं।

चूँकि वर्गीकरण के लिए भाषा समर्थन अधिक सर्वव्यापी है, तथा गति में कमी के अतिरिक्त वर्गीकरण का सरलीकृत दृष्टिकोण जिसके बाद अनुक्रमण किया जाता है, कई वातावरणों में समान किया जाता है। वास्तव में अनुद्योगी मूल्यांकन के लिए, यह सरलीकृत दृष्टिकोण k सबसे छोटी/सबसे बड़ी क्रमबद्ध (विशेष स्थिति के रूप में अधिकतम/न्यूनतम के साथ) के लिए संभव सर्वोत्तम जटिलता भी प्राप्त कर सकता है यदि क्रम पर्याप्त अनुद्योगी है।^{[citation needed]}.

यह भी देखें

संदर्भ

↑ Lai T.W., Wood D. (1988) Implicit selection. In: Karlsson R., Lingas A. (eds) SWAT 88. SWAT 1988. Lecture Notes in Computer Science, vol 318. Springer, Berlin, Heidelberg
↑ Section 25.3.2 of ISO/IEC 14882:2003(E) and 14882:1998(E)
↑ nth_element, SGI STL
↑ "Python - heapq.nlargest की समय जटिलता क्या है?".

ग्रन्थसूची

Blum, M.; Floyd, R. W.; Pratt, V. R.; Rivest, R. L.; Tarjan, R. E. (August 1973). "Time bounds for selection" (PDF). Journal of Computer and System Sciences. 7 (4): 448–461. doi:10.1016/S0022-0000(73)80033-9.
Floyd, R. W.; Rivest, R. L. (March 1975). "Expected time bounds for selection". Communications of the ACM. 18 (3): 165–172. doi:10.1145/360680.360691. S2CID 3064709.
Kiwiel, K. C. (2005). "On Floyd and Rivest's SELECT algorithm". Theoretical Computer Science. 347 (1–2): 214–238. doi:10.1016/j.tcs.2005.06.032.
Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.3.3: Minimum-Comparison Selection, pp. 207–219.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 9: Medians and Order Statistics, pp. 183–196. Section 14.1: Dynamic order statistics, pp. 302–308.
This article incorporates public domain material from Black, Paul E. "Select". Dictionary of Algorithms and Data Structures.

बाहरी संबंध

"Lecture notes for January 25, 1996: Selection and order statistics", ICS 161: Design and Analysis of Algorithms, David Eppstein

[1] Lai T.W., Wood D. (1988) Implicit selection. In: Karlsson R., Lingas A. (eds) SWAT 88. SWAT 1988. Lecture Notes in Computer Science, vol 318. Springer, Berlin, Heidelberg

[2] Section 25.3.2 of ISO/IEC 14882:2003(E) and 14882:1998(E)

[3] th_element, SGI STL

[4] "Python - heapq.nlargest की समय जटिलता क्या है?".

[1]

[2]

[3]

[4]

@@ Line 2: / Line 2: @@
 {{for|अनुवांशिक एल्गोरिदम में कृत्रिम प्राकृतिक चयन|चयन (आनुवंशिक एल्गोरिथम)}}
 {{more footnotes|date=जुलाई 2017}}
-[[ कंप्यूटर विज्ञान |'''''कंप्यूटर विज्ञान''''']]  '''''में''''', एक चयन एल्गोरिदम की  [[सूची (सार डेटा प्रकार)|सूची]]  या सरणी में k वें सबसे छोटी संख्या खोजने के लिए एल्गोरिदम है। इस तरह की संख्या को k वें  ''[[ 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 सबसे बड़े तत्वों का चयन करने के लिए  [[ आंशिक छँटाई |आंशिक वर्गीकरण]]  का उपयोग कर सकते हैं। k वें सबसे छोटा (resp., k वें सबसे बड़ा तत्व) तब आंशिक रूप से क्रमबद्ध सूची का सबसे बड़ा (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) की स्पर्शोन्मुख जटिलता उत्पन्न करता है। वास्तव में विभाजन-आधारित चयन एल्गोरिदम स्वयं k वें सबसे छोटा तत्व तथा k सबसे छोटा तत्व अन्य (तत्वों के क्रम में नहीं) दोनों को उत्पन्न करता है। यह O(''n'') time में किया जा सकता है - शीघ्र चयन की औसत जटिलता और परिष्कृत विभाजन-आधारित चयन एल्गोरिदम की सबसे खराब जटिलता की स्थिति होती है।
+यदि आंशिक वर्गीकरण को तनाव मुक्त किया जाता है, जिससे k सबसे छोटे तत्व लौटाए जाते हैं, लेकिन O(k log k) के क्रम में कारक को समाप्त नहीं किया जा सकता है। एक अतिरिक्त अधिकतम चयन (O(k) समय की आवश्यक होती है, लेकिन  <math>k \leq n</math> यह अभी भी O(n) की स्पर्शोन्मुख जटिलता को उत्पन्न करता है। वास्तव में विभाजन-आधारित चयन एल्गोरिदम स्वयं kth सबसे छोटा तत्व अन्य तत्वों के क्रम में दोनों को उत्पन्न नहीं करता है। यह O(''n'') time में ही किया जा सकता है - शीघ्र चयन की औसत जटिलता और परिष्कृत विभाजन-आधारित चयन एल्गोरिदम की सबसे खराब जटिलता की स्थिति होती है।
-इसके विपरीत एक चयन एल्गोरिदम दिया गया है, O(''n'') time में सूची के माध्यम से पुनरावृत्ति करके और k वें तत्व से कम सभी तत्वों को रिकॉर्ड करके आसानी से एक अनियंत्रित आंशिक वर्गीकरण (के सबसे छोटे तत्व, क्रम में नहीं) प्राप्त कर सकते हैं। यदि इसका परिणाम k − 1 तत्वों से कम होता है, तो कोई भी शेष तत्व k वें तत्व के बराबर होता है। तत्वों की समानता की संभावना के कारण सावधानी बरतनी चाहिए। तथा k वें तत्व से कम या उसके बराबर सभी तत्वों को सम्मिलित नहीं करना चाहिए, क्योंकि k वें तत्व से बड़े तत्व भी इसके बराबर हो सकते हैं।
+इसके विपरीत एक चयन एल्गोरिदम दिया गया है, जो O(''n'') time में सूची के माध्यम से पुनरावृत्ति करके और kth तत्व से कम सभी तत्वों को रिकॉर्ड करके आसानी से एक अनियंत्रित आंशिक वर्गीकरण (के सबसे छोटे तत्व, क्रम में नहीं) प्राप्त कर सकते हैं। यदि इसका परिणाम k − 1 तत्वों से कम होता है, तो कोई भी शेष तत्व kth तत्व के बराबर होता है। तत्वों की समानता की संभावना के कारण सावधानी रखना चाहिए, तथा kth तत्व से कम या उसके बराबर सभी तत्वों को सम्मिलित नहीं करना चाहिए, क्योंकि kth तत्व से बड़े तत्व भी इसके बराबर हो सकते हैं।
-इस प्रकार अनियंत्रित आंशिक वर्गीकरण (न्यूनतम k तत्व, लेकिन आदेशित नहीं) और k वें तत्व का चयन बहुत समान समस्याएँ होती हैं। न केवल उनके पास समान स्पर्शोन्मुख जटिलता है, O(n), लेकिन दोनों में से किसी एक के समाधान को सीधा एल्गोरिथ्म द्वारा दूसरे के समाधान में परिवर्तित किया जा सकता है। अधिकतम k तत्व ढूँढना या k वें तत्व के मान के वर्गीकरण के नीचे सूची के तत्वों को फ़िल्टर करना होता है।
+इस प्रकार अनियंत्रित आंशिक वर्गीकरण (न्यूनतम k तत्व, लेकिन आदेशित नहीं) और kth तत्व का चयन बहुत समान समस्याएँ होती हैं। न केवल उनके पास समान स्पर्शोन्मुख जटिलता है, O(n), लेकिन दोनों में से किसी एक के समाधान को सीधा एल्गोरिथ्म द्वारा दूसरे के समाधान में परिवर्तित किया जा सकता है। अधिकतम k तत्व ढूँढना या kth तत्व के मान के वर्गीकरण के नीचे सूची के तत्वों को फ़िल्टर करना होता है।
-=== आंशिक चयन प्रकार ===
+=== आंशिक चयन का प्रकार ===
 आंशिक वर्गीकरण द्वारा चयन का एक सरल उदाहरण आंशिक चयन वर्गीकरण का उपयोग करना है।
 न्यूनतम (प्रतिक्रिया अधिकतम) खोजने के लिए स्पष्ट रैखिक समय एल्गोरिदम - सूची पर पुनरावृत्ति करना और अब तक के सभी न्यूनतम (प्रतिक्रिया अधिकतम) तत्व का ट्रैक रखना - आंशिक चयन प्रकार के रूप में देखा जा सकता है, जो कि 1 सबसे छोटा तत्व चुनता है। हालांकि स्थिति k = 1 के लिए कई अन्य आंशिक प्रकार से भी इस एल्गोरिदम को कम करते हैं, जैसे आंशिक हीप वर्गीकरण।
-अधिक सामान्य रूप से एक आंशिक चयन वर्गीकरण सरल चयन एल्गोरिदम उत्पन्न करता है, जो O(''kn'') time लेता है। यह असम्बद्ध रूप से अप्रभावी होता है, लेकिन पर्याप्त रूप से कुशल हो सकता है यदि k छोटा है, तथा लागू करना आसान है। विशेष रूप से हम केवल एसके न्यूनतम मान को पाते हैं और इसे प्रारम्भ में ले जाते हैं, शेष सूची में तब तक दोहराते हैं जब तक कि हम k तत्वों को संचित नहीं कर लेते हैं, और फिर k वें तत्व को वापस कर देते हैं। यहआंशिक चयन वर्गीकरण-आधारित एल्गोरिथम होता है।
+अधिक सामान्य रूप से एक आंशिक चयन वर्गीकरण सरल चयन एल्गोरिदम उत्पन्न करता है, जो O(''kn'') time लेता है। यह असम्बद्ध रूप से अप्रभावी होता है, लेकिन पर्याप्त रूप से कुशल हो सकता है यदि k छोटा है, तथा लागू करना आसान है। विशेष रूप से हम केवल एसके न्यूनतम मान को पाते हैं और इसे प्रारम्भ में ले जाते हैं, शेष सूची में तब तक दोहराते हैं जब तक कि हम k तत्वों को संचित नहीं कर लेते हैं, और फिर kth तत्व को वापस कर देते हैं। यह आंशिक चयन वर्गीकरण-आधारित एल्गोरिथम मे होता है।
   '''function''' select(list[1..n], k)
       '''for''' i '''from''' 1 '''to''' k
@@ Line 38: / Line 38: @@
 {{further|शीघ्र चयन}}
-रैखिक प्रदर्शन विभाजन-आधारित चयन एल्गोरिदम द्वारा प्राप्त किया जा सकता है, सबसे मूल रूप से शीघ्र चयन शीघ्र वर्गीकरण का एक प्रकार है - दोनों में एक मुख्य आधार को चुनता है।  तथा इसके द्वारा डेटा का विभाजन करता है, लेकिन जब शीघ्र वर्गीकरण विभाजन के दोनों किनारों पर पुनरावृत्ति करता है, तो शीघ्र चयन केवल एक तरफ की पुनरावृत्ति करता है, अर्थात् वह पक्ष जिस पर वांछित kth तत्व होता है। शीघ्र वर्गीकरण के साथ इसका सर्वोत्त्म औसत प्रदर्शन है, इस स्थिति में रैखिक, लेकिन सबसे खराब प्रदर्शन इस परिस्थिति में द्विघात होता है। यह उदाहरण के लिए पहले तत्व को आधार के रूप में लेने और अधिकतम तत्व की खोज करने से होता है, यदि डेटा पहले से ही क्रमबद्ध होता है। तो व्यावहारिक रूप से एक यादृच्छिक तत्व को धुरी के रूप में चुनकर इससे बचा जा सकता है, जो  [[ लगभग निश्चित |लगभग निश्चित]]  रैखिक प्रदर्शन को उत्पन्न करता है। वैकल्पिक रूप से, एक अधिक सावधान नियतात्मक धुरी रणनीति का उपयोग किया जा सकता है, जैसे कि माध्यिका की माध्यिका ये हाइब्रिड  [[ अंतर्चयन |अंतर्चयन]]  एल्गोरिथम ([[ introsort |अन्तर्मुखी]]  के अनुरूप) में संयुक्त हैं, जो शीघ्र चयन के साथ प्रारम्भ होता है, लेकिन यदि प्रगति धीमी होती है, तो माध्यिका के मध्य में वापस आ जाता है, जिसके परिणामस्वरूप O(''n'') का तेज औसत प्रदर्शन और सर्वोत्त्म सबसे खराब प्रदर्शन दोनों होता है।
+रैखिक प्रदर्शन विभाजन-आधारित चयन एल्गोरिदम द्वारा प्राप्त किया जा सकता है, सबसे मूल रूप से शीघ्र चयन एवं शीघ्र वर्गीकरण का एक प्रकार होता है, जो दोनों में से एक मुख्य आधार को चुनता है।  तथा इसके द्वारा डेटा का विभाजन करता है, लेकिन जब शीघ्र वर्गीकरण विभाजन के दोनों किनारों पर पुनरावृत्ति करता है, तो शीघ्र चयन केवल एक तरफ की पुनरावृत्ति करता है, अर्थात् वह पक्ष जिस पर वांछित kth तत्व होता है। शीघ्र वर्गीकरण के साथ इसका सर्वोत्त्म औसत प्रदर्शन है, इस स्थिति में रैखिक, लेकिन सबसे खराब प्रदर्शन इस परिस्थिति में द्विघात होता है। यह उदाहरण के लिए पहले तत्व को आधार के रूप में लेने और अधिकतम तत्व की खोज करने से होता है, यदि डेटा पहले से ही क्रमबद्ध होता है। तो व्यावहारिक रूप से एक यादृच्छिक तत्व को धुरी के रूप में चुनकर इससे बचा जा सकता है, जो  [[ लगभग निश्चित |लगभग निश्चित]]  रैखिक प्रदर्शन को उत्पन्न करता है। वैकल्पिक रूप से, एक अधिक सावधान नियतात्मक धुरी रणनीति का उपयोग किया जा सकता है, जैसे कि माध्यिका की माध्यिका ये हाइब्रिड  [[ अंतर्चयन |अंतर्चयन]]  एल्गोरिथम ([[ introsort |अन्तर्मुखी]]  के अनुरूप) में संयुक्त हैं, जो शीघ्र चयन के साथ प्रारम्भ होता है, लेकिन यदि प्रगति धीमी होती है, तो माध्यिका के मध्य में वापस आ जाता है, जिसके परिणामस्वरूप O(''n'') का तेज औसत प्रदर्शन और सर्वोत्त्म सबसे खराब प्रदर्शन दोनों होता है।
 विभाजन-आधारित एल्गोरिदम सामान्य रूप से जगह में किया जाता है, जिसके परिणामस्वरूप डेटा को आंशिक रूप से वर्गीकरण किया जाता है। O(n) अतिरिक्त स्थान की कीमत पर मूल डेटा को बदले बिना, उन्हें जगह से बाहर किया जा सकता है।
@@ Line 44: / Line 44: @@
 === महत्वपूर्ण योजना के रूप में मध्यस्थ चयन ===
 {{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)। माध्यिका वर्गीकरण के लिए सबसे अच्छी धुरी है, क्योंकि यह समान रूप से डेटा को विभाजित करती है, और इस प्रकार सर्वोत्तम वर्गीकरण का दायित्व देती है, यह मानते हुए कि चयन एल्गोरिथ्म सर्वोत्तम है। शीघ्र वर्गीकरण में महत्वपूर्ण योजना अनुमानित माध्य का उपयोग करते हुए, मध्यस्थ की माध्यिका के लिए एक वर्गीकरण एनालॉग उपस्थित होते है, और इसी तरह एक सर्वोत्तम शीघ्र वर्गीकरण उत्पन्न करता है।
-== चयन द्वारा वृद्धिशील छँटाई ==
+== चयन द्वारा वृद्धिशील वर्गीकरण ==
-छँटाई द्वारा चयन के विपरीत, बार-बार चयन द्वारा क्रमिक रूप से क्रमबद्ध किया जा सकता है। संक्षेप में, चयन केवल एक तत्व, k वें तत्व उत्पन्न करता है। हालांकि, व्यावहारिक चयन एल्गोरिदम में अक्सर आंशिक छँटाई शामिल होती है, या ऐसा करने के लिए संशोधित किया जा सकता है। आंशिक छँटाई द्वारा चयन स्वाभाविक रूप से ऐसा करता है, तत्वों को k तक छाँटता है, और विभाजन द्वारा चयन भी कुछ तत्वों को छाँटता है: पिवोट्स को सही स्थिति में क्रमबद्ध किया जाता है, जिसमें k वें तत्व अंतिम धुरी होता है, और पिवोट्स के बीच के तत्वों का मान होता है धुरी मूल्यों के बीच। विभाजन-आधारित चयन और विभाजन-आधारित छँटाई के बीच का अंतर, जैसा कि Quickselect बनाम Quicksort में है, यह है कि चयन में प्रत्येक धुरी के केवल एक तरफ रिकर्स करता है, केवल पिवोट्स को छांटता है (औसतन लॉग (एन) पिवोट्स का उपयोग किया जाता है), धुरी के दोनों किनारों पर पुनरावर्ती होने के बजाय।
+वर्गीकरण द्वारा चयन के विपरीत बार-बार चयन द्वारा क्रमिक रूप से क्रमबद्ध किया जा सकता है। संक्षेप में चयन केवल एक तत्व kth तत्व उत्पन्न करता है। हालांकि, व्यावहारिक चयन एल्गोरिदम में अधिकांश आंशिक वर्गीकरण सम्मिलित होता है, ऐसा करने के लिए इसको संशोधित भी किया जा सकता है। आंशिक वर्गीकरण द्वारा चयन स्वाभाविक रूप से ऐसा करता है, तत्वों को k तक क्रमबद्ध करना और विभाजन द्वारा चयन करना भी कुछ तत्वों को क्रमबद्ध करता है। पिवोट्स को सही स्थिति में क्रमबद्ध किया जाता है, जिसमें kth तत्व अंतिम केंद्र होता है, और पिवोट्स के बीच के तत्वों का मान होता है धुरी मानो के बीच विभाजन-आधारित चयन और विभाजन-आधारित वर्गीकरण के बीच का अंतर जैसा कि शीघ्र चयन बनाम शीघ्र वर्गीकरण में होता है चयन में प्रत्येक धुरी के केवल एक तरफ पुनरावृत्ति होती है, केवल पिवोट्स को वर्गीकरण करना (औसत log(''n'') पिवोट्स का उपयोग किया जाता है, धुरी के दोनों किनारों पर पुनरावर्ती होने के अतिरिक्त।
-इसका उपयोग उसी डेटा पर बाद के चयनों को गति देने के लिए किया जा सकता है; चरम में, एक पूरी तरह से क्रमबद्ध सरणी ओ (1) चयन की अनुमति देती है। इसके अलावा, पहले एक पूर्ण सॉर्ट करने की तुलना में, बार-बार चयन द्वारा क्रमिक रूप से सॉर्ट करना परिशोधन विश्लेषण कई चयनों पर सॉर्टिंग लागत।
+इसका उपयोग उसी डेटा पर बाद के चयनों को गति देने के लिए किया जा सकता है। तीव्र में पूरी तरह से क्रमबद्ध सरणी O(1) चयन की अनुमति देती है। इसके अतिरिक्त पहले एक पूर्ण वर्गीकरण करने की तुलना में बार-बार चयन द्वारा वृद्धिशील छँटाई कई चयनों पर वर्गीकरण लागत को परिशोधित करती है।
-आंशिक रूप से सॉर्ट किए गए डेटा (k तक) के लिए, जब तक आंशिक रूप से सॉर्ट किया गया डेटा और इंडेक्स k जिस तक डेटा सॉर्ट किया जाता है, रिकॉर्ड किया जाता है, k से कम या उसके बराबर j के बाद के चयन केवल jth तत्व का चयन कर सकते हैं, क्योंकि यह पहले से ही सॉर्ट किया गया है, जबकि k से बड़ा j का चयन केवल k वें स्थिति से ऊपर के तत्वों को सॉर्ट करने की आवश्यकता है।
+आंशिक रूप से वर्गीकरण किए गए डेटा K तक के लिए, जब तक आंशिक रूप से वर्गीकृत किए गए डेटा और इंडेक्स के तक डेटा वर्गीकरण किया जाता है, तब तक रिकॉर्ड किया जाता है, k से कम या उसके बराबर j के बाद के चयन केवल jth तत्व का चयन कर सकते हैं, क्योंकि यह पहले से ही वर्गीकरण किया गया है, जबकि k से अधिक j के चयनों को केवल kth स्थिति से ऊपर के तत्वों को वर्गीकृत करने की आवश्यकता है
-विभाजित डेटा के लिए, यदि पिवोट्स की सूची संग्रहीत की जाती है (उदाहरण के लिए, सूचकांकों की एक क्रमबद्ध सूची में), तो बाद के चयनों को केवल दो पिवोट्स (नीचे और ऊपर के निकटतम पिवोट्स) के बीच के अंतराल में चयन करने की आवश्यकता होती है। सबसे बड़ा लाभ शीर्ष-स्तरीय पिवोट्स से है, जो महंगे बड़े विभाजनों को समाप्त करता है: डेटा के मध्य के पास एक एकल पिवट भविष्य के चयन के लिए समय को आधा कर देता है। बाद के चयनों पर पिवट सूची बढ़ेगी, क्योंकि डेटा अधिक क्रमबद्ध हो जाता है, और यहां तक कि एक पूर्ण प्रकार के आधार के रूप में विभाजन-आधारित सॉर्ट को भी पास किया जा सकता है।
+विभाजित डेटा के लिए, यदि पिवोट्स की सूची संग्रहीत की जाती है (उदाहरण के लिए, सूचकांकों की एक क्रमबद्ध सूची में), तो बाद के चयनों को केवल दो पिवोट्स (निकटतम पिवोट्स नीचे और ऊपर) के बीच अंतराल में चयन करने की आवश्यकता होती है। सबसे बड़ा लाभ शीर्ष-स्तर के पिवोट्स से है, जो महंगे बड़े विभाजनों को समाप्त करते हैं। डेटा के मध्य के पास एक एकल पिवट (धुरी) भविष्य के चयनों के लिए आधे समय में कटौती करता है। पिवट सूची बाद के चयनों में बढ़ेगी, क्योंकि डेटा अधिक क्रमबद्ध हो जाता है, और एक पूर्ण वर्गीकृत के आधार के रूप में विभाजन-आधारित वर्गीकृत में भी पास किया जा सकता है।
-== उपरेखीय समय == में चयन करने के लिए डेटा संरचनाओं का उपयोग करना
+== उप-रेखीय समय में चयन करने के लिए डेटा संरचनाओं का उपयोग करना ==
-डेटा की एक असंगठित सूची को देखते हुए, न्यूनतम तत्व को खोजने के लिए रैखिक समय (Ω(n)) की आवश्यकता होती है, क्योंकि हमें प्रत्येक तत्व की जांच करनी होती है (अन्यथा, हम इसे याद कर सकते हैं)। यदि हम सूची को व्यवस्थित करते हैं, उदाहरण के लिए इसे हर समय क्रमबद्ध करके रखते हैं, तो k वें सबसे बड़ा तत्व का चयन करना तुच्छ है, लेकिन फिर सम्मिलन के लिए रैखिक समय की आवश्यकता होती है, जैसा कि दो सूचियों के संयोजन जैसे अन्य कार्यों में होता है।
+डेटा की एक असंगठित सूची को देखते हुए, न्यूनतम तत्व को खोजने के लिए रैखिक समय (Ω(n)) की आवश्यकता होती है, क्योंकि हमें प्रत्येक तत्व की जांच करनी होती है (अन्यथा, हम इसे याद कर सकते हैं)। यदि हम सूची को व्यवस्थित करते हैं, उदाहरण के लिए इसे प्रत्येक समय क्रमबद्ध करके रखते हैं, तो kth सबसे बड़ा तत्व का चयन करना तुच्छ है, लेकिन फिर सम्मिलन के लिए रैखिक समय की आवश्यकता होती है, जैसा कि दो सूचियों के संयोजन जैसे अन्य कार्यों में होता है।
-उपरैखिक समय में एक आदेश आंकड़े खोजने की रणनीति उपयुक्त डेटा संरचनाओं का उपयोग करके डेटा को एक संगठित फैशन में संग्रहित करना है जो चयन की सुविधा प्रदान करता है। ऐसी दो डेटा संरचनाएँ ट्री-आधारित संरचनाएँ और फ़्रीक्वेंसी टेबल हैं।
+उपरैखिक समय में एक आदेश आंकड़े खोजने की रणनीति उपयुक्त डेटा संरचनाओं का उपयोग करके डेटा को एक संगठित फैशन में संग्रहित करना है जो चयन की सुविधा प्रदान करता है। ऐसी दो डेटा संरचनाएँ ट्री-आधारित संरचनाएँ और आवृत्ति तालिकाएँ होती हैं।
-जब केवल न्यूनतम (या अधिकतम) की आवश्यकता होती है, तो हीप (डेटा संरचना) का उपयोग करने के लिए एक अच्छा तरीका है, जो निरंतर समय में न्यूनतम (या अधिकतम) तत्व खोजने में सक्षम है, जबकि सम्मिलन सहित अन्य सभी ऑपरेशन ओ हैं (लॉग एन) या बेहतर। अधिक आम तौर पर, एक [[ स्व-संतुलन बाइनरी सर्च ट्री ]] को आसानी से संवर्धित किया जा सकता है ताकि एक तत्व को सम्मिलित करना और O(log n) समय में k वें सबसे बड़ा तत्व खोजना संभव हो सके; इसे [[ ऑर्डर स्टेटिस्टिक ट्री ]] कहा जाता है। हम बस प्रत्येक नोड में कितने वंशज हैं, इसकी गिनती करते हैं, और इसका उपयोग यह निर्धारित करने के लिए करते हैं कि किस पथ का अनुसरण करना है। सूचना को कुशलता से अपडेट किया जा सकता है क्योंकि एक नोड को जोड़ने से केवल इसके ओ (लॉग एन) पूर्वजों की संख्या प्रभावित होती है, और पेड़ के घुमाव केवल रोटेशन में शामिल नोड्स की गिनती को प्रभावित करते हैं।
+जब केवल न्यूनतम या अधिकतम की आवश्यकता होती है, तो ढेर का उपयोग करने के लिए एक अच्छा तरीका होता है, जो निरंतर समय में न्यूनतम या अधिकतम तत्व खोजने में सक्षम होता है, जबकि सम्मिलन समेत अन्य सभी संचालन O(log ''n'') होते हैं। या अधिक सामान्य रूप से एक [[ स्व-संतुलन बाइनरी सर्च ट्री | स्व-संतुलन बाइनरी सर्च ट्री]]  को सरलता से संवर्धित किया जा सकता है, ताकि एक तत्व को सम्मिलित करना और O(log n) समय में kth सबसे बड़ा तत्व खोजना संभव हो सके।  इसे  [[ ऑर्डर स्टेटिस्टिक ट्री |ऑर्डर स्टेटिस्टिक ट्री]]  कहा जाता है। हम बस प्रत्येक बिंदु में कितने संतति हैं, इसकी गिनती करते हैं, और इसका उपयोग यह निर्धारित करने के लिए करते हैं कि किस पथ का अनुसरण करना है। सूचना को कुशलता से अपडेट किया जा सकता है क्योंकि एक नोड को जोड़ने से केवल इसके O(log ''n'') पूर्वजों की संख्या प्रभावित होती है, और ट्री के घुमाव केवल रोटेशन में सम्मिलित बिंदु की गिनती को प्रभावित करते हैं।
-एक और सरल रणनीति [[ हैश टेबल ]] जैसी कुछ अवधारणाओं पर आधारित है। जब हम पहले से मानों की श्रेणी जानते हैं, तो हम उस श्रेणी को h उपअंतरालों में विभाजित कर सकते हैं और इन्हें h बकेट को असाइन कर सकते हैं। जब हम कोई तत्व डालते हैं, तो हम इसे उस अंतराल के अनुरूप बाल्टी में जोड़ते हैं जिसमें यह गिरता है। न्यूनतम या अधिकतम तत्व खोजने के लिए, हम पहली खाली बाल्टी के लिए शुरुआत या अंत से स्कैन करते हैं और उस बाल्टी में न्यूनतम या अधिकतम तत्व ढूंढते हैं। . सामान्य तौर पर, k वें तत्व को खोजने के लिए, हम प्रत्येक बकेट में तत्वों की संख्या की गिनती बनाए रखते हैं, फिर बकेट को बाएं से दाएं जोड़कर तब तक स्कैन करते हैं जब तक कि हमें वांछित तत्व वाली बकेट नहीं मिल जाती है, फिर अपेक्षित रैखिक-समय का उपयोग करें एल्गोरिदम उस बाल्टी में सही तत्व खोजने के लिए।
+एक और सरल योजना  [[ हैश टेबल |द्रुतान्वेषण सारणी]]  जैसी कुछ अवधारणाओं पर आधारित है। जब हम पहले से मानों की श्रेणी जानते हैं, तो हम उस श्रेणी को h उपअंतरालों में विभाजित कर सकते हैं और इन्हें h बकेट को नियुक्त कर सकते हैं। जब हम कोई तत्व को डालते हैं, तो हम इसे उस अंतराल के अनुरूप बकेट में जोड़ते हैं, जिसमें यह गिरता है। न्यूनतम या अधिकतम तत्व खोजने के लिए, हम पहली खाली बकेट के लिए प्रारम्भ या अंत से स्कैन करते हैं, और उस बकेट में न्यूनतम या अधिकतम तत्व खोजते हैं। सामान्य रूप से kth तत्व को खोजने के लिए, हम प्रत्येक बकेट में तत्वों की संख्या की गिनती बनाए रखते हैं, फिर बकेट को बाएं से दाएं जोड़ते हुए स्कैन करें जब तक कि हमें वांछित तत्व वाली बकेट न मिल जाए, फिर उस बकेट में सही तत्व को खोजने के लिए अपेक्षित रैखिक-समय एल्गोरिथ्म का उपयोग करते है।
-यदि हम लगभग sqrt(n) आकार का h चुनते हैं, और इनपुट समान रूप से वितरित होने के करीब है, तो यह योजना अपेक्षित O(sqrt(n)) समय में चयन कर सकती है। दुर्भाग्य से, यह रणनीति एक संकीर्ण अंतराल में तत्वों के क्लस्टरिंग के प्रति भी संवेदनशील है, जिसके परिणामस्वरूप बड़ी संख्या में तत्व हो सकते हैं (क्लस्टरिंग को एक अच्छे हैश फ़ंक्शन के माध्यम से समाप्त किया जा सकता है, लेकिन k वें सबसे बड़े हैश मान वाले तत्व को खोजना नहीं है) बहुत उपयोगी)। इसके अतिरिक्त, हैश तालिकाओं की तरह इस संरचना को दक्षता बनाए रखने के लिए तालिका आकार बदलने की आवश्यकता होती है क्योंकि तत्व जोड़े जाते हैं और n h से बहुत बड़ा हो जाता है<sup>2</उप>। इसका एक उपयोगी मामला डेटा की एक परिमित सीमा में ऑर्डर स्टेटिस्टिक या एक्सट्रीमम ढूंढ रहा है। बकेट अंतराल 1 के साथ उपरोक्त तालिका का उपयोग करना और प्रत्येक बकेट में गिनती बनाए रखना अन्य तरीकों से बहुत बेहतर है। ऐसी हैश तालिकाएँ वर्णनात्मक आँकड़ों में डेटा को वर्गीकृत करने के लिए उपयोग की जाने वाली आवृत्ति तालिकाओं की तरह होती हैं।
+यदि हम लगभग sqrt(n) आकार का h चुनते हैं, और इनपुट समान रूप से वितरित होने के नजदीक होता है, तो यह योजना अपेक्षित O(sqrt(n)) समय में चयन कर सकती है। दुर्भाग्य से यह योजना एक संकीर्ण अंतराल में तत्वों के ( गुच्छन) क्लस्टरिंग के प्रति भी संवेदनशील होती है, जिसके परिणामस्वरूप बड़ी संख्या में तत्व हो सकते हैं। क्लस्टरिंग को एक अच्छे हैश फलन के माध्यम से समाप्त किया जा सकता है, लेकिन kth सबसे बड़े हैश मान वाले तत्व को खोजना बहुत उपयोगी नहीं है। इसके अतिरिक्त हैश तालिकाओं की तरह इस संरचना को दक्षता बनाए रखने के लिए तालिका का आकार मे परिवर्तन की आवश्यकता होती है, क्योंकि जब तत्व जोड़े जाते हैं, तो n, h<sup>2</sup> से बहुत बड़ा हो जाता है। जिसका एक उपयोगी स्थिति डेटा को एक परिमित सीमा में आदेशित आँकड़ा को अत्यधिक ढूंढ रहा होता है। बकेट अंतराल 1 के साथ उपरोक्त तालिका का उपयोग करना और प्रत्येक बकेट में गिनती बनाए रखना अन्य तरीकों से बहुत अच्छा होता है। ऐसी हैश तालिकाएँ वर्णनात्मक आँकड़ों में डेटा को वर्गीकृत करने के लिए उपयोग की जाने वाली आवृत्ति तालिकाओं की तरह होती हैं।
 == निचली सीमा ==
 {{anchor|Tournament Algorithm}}
-[[ कंप्यूटर प्रोग्रामिंग की कला ]] में, डोनाल्ड ई। नुथ ने n वस्तुओं की एक असंगठित सूची (केवल तुलनाओं का उपयोग करके) की सबसे छोटी प्रविष्टियों का पता लगाने के लिए आवश्यक तुलनाओं की संख्या के लिए कई निचली सीमाओं पर चर्चा की। न्यूनतम या अधिकतम प्रविष्टि के लिए n - 1 की एक तुच्छ निचली सीमा है। इसे देखने के लिए, एक टूर्नामेंट पर विचार करें जहां प्रत्येक गेम एक तुलना का प्रतिनिधित्व करता है। चूंकि टूर्नामेंट के विजेता को छोड़कर प्रत्येक खिलाड़ी को विजेता को जानने से पहले एक गेम हारना होगा, हमारे पास n - 1 तुलनाओं की निचली सीमा है।
-अन्य इंडेक्स के लिए कहानी और अधिक जटिल हो जाती है। हम परिभाषित करते हैं <math>W_{t}(n)</math> t सबसे छोटे मानों को खोजने के लिए आवश्यक तुलनाओं की न्यूनतम संख्या के रूप में। नुथ एस.एस. किसलिट्सिन द्वारा प्रकाशित एक पेपर का संदर्भ देता है, जो इस मूल्य पर एक ऊपरी सीमा दिखाता है:
+[[ कंप्यूटर प्रोग्रामिंग की कला |कंप्यूटर प्रोग्रामिंग की कला]]  डोनाल्ड ई. नुथ ने n पदों की असंगठित सूची की सबसे छोटी प्रविष्टियों का पता लगाने के लिए आवश्यक तुलनाओं की संख्या के लिए कई निचली सीमाओं पर चर्चा की (केवल तुलनाओं का उपयोग करके)। न्यूनतम या अधिकतम प्रविष्टि के लिए n − 1 की एक तुच्छ निचली सीमा है। इसे देखने के लिए एक खेलकूद-प्रतियोगिता पर विचार करें, क्योंकि जहां प्रत्येक खेल एक तुलना का प्रतिनिधित्व करता है। चूंकि खेलकूद-प्रतियोगिता के विजेता को छोड़कर प्रत्येक खिलाड़ी को विजेता को जानने से पहले एक खेल को हारना चाहिए, हमारे पास n - 1 तुलनाओं की निचली सीमा है।
+अन्य अनुक्रमणिकाओं के लिए कहानी अधिक जटिल हो जाती है। हम <math>W_{t}(n)</math> को t के सबसे छोटे मानों को खोजने के लिए आवश्यक तुलनाओं की न्यूनतम संख्या के रूप में परिभाषित करते हैं। नुथ एस.एस. किस्लिट्सिन द्वारा प्रकाशित लेख का संदर्भ देता है, जो इस मान पर एक ऊपरी सीमा को दर्शाता है।
 :<math>W_{t}(n) \leq n - t + \sum_{n+1-t < j \leq n} \lceil{\log_2\, j}\rceil \quad \text{for}\, n \geq t</math>
-यह सीमा टी = 2 के लिए प्राप्त करने योग्य है लेकिन बेहतर, अधिक जटिल सीमाएं बड़े टी के लिए जानी जाती हैं।{{citation needed|date=April 2018}}
+यह बाउंड t=2 के लिए प्राप्त करने योग्य है लेकिन बेहतर, अधिक जटिल बाउंड बड़े t के लिए जाने जाते हैं।{{citation needed|date=April 2018}}
 == अंतरिक्ष जटिलता ==
-चयन की आवश्यक स्थान जटिलता ओ (1) अतिरिक्त भंडारण है, जिसमें उस सरणी को संग्रहीत करने के अलावा जिसमें चयन किया जा रहा है। इष्टतम O(n) समय जटिलता को संरक्षित करते हुए ऐसी अंतरिक्ष जटिलता प्राप्त की जा सकती है।<ref>Lai T.W., Wood D. (1988) Implicit selection. In: Karlsson R., Lingas A. (eds) SWAT 88. SWAT 1988. Lecture Notes in Computer Science, vol 318. Springer, Berlin, Heidelberg</ref>
+चयन की आवश्यक स्थान जटिलता O(1) अतिरिक्त भंडारण है, जिसमें उस सरणी को संग्रहीत करने के अतिरिक्त जिसमें चयन किया जा रहा है। सर्वोत्तम O(n) समय जटिलता को बनाए रखते हुए ऐसी अंतरिक्ष जटिलता प्राप्त की जा सकती है।<ref>Lai T.W., Wood D. (1988) Implicit selection. In: Karlsson R., Lingas A. (eds) SWAT 88. SWAT 1988. Lecture Notes in Computer Science, vol 318. Springer, Berlin, Heidelberg</ref>
-{{Expand section|date=January 2019}}
+{{Expand section|date=जनवरी 2019}}
 == ऑनलाइन चयन एल्गोरिथ्म ==
-[[ ऑनलाइन एल्गोरिदम ]] चयन एक धारा के सबसे छोटे तत्व की गणना करने के लिए संकीर्ण रूप से संदर्भित हो सकता है, इस मामले में आंशिक छँटाई एल्गोरिदम - k + O (1) स्थान के साथ k अब तक के सबसे छोटे तत्वों के लिए - का उपयोग किया जा सकता है, लेकिन विभाजन-आधारित एल्गोरिदम नहीं हो सकता .
+[[ ऑनलाइन एल्गोरिदम ]] एक धारा के kth सबसे छोटे तत्व की गणना करने के लिए संकीर्ण रूप से संदर्भित हो सकता है, इस स्थिति में आंशिक वर्गीकृत एल्गोरिदम - k + O (1) के साथ k सबसे छोटे तत्वों के लिए अब तक का उपयोग किया जा सकता है, लेकिन विभाजन-आधारित एल्गोरिदम नहीं हो सकता है।
-वैकल्पिक रूप से, चयन के लिए स्वयं ऑनलाइन एल्गोरिथम होना आवश्यक हो सकता है, अर्थात, एक तत्व को केवल अवलोकन के उदाहरण पर अनुक्रमिक इनपुट से चुना जा सकता है और प्रत्येक चयन, क्रमशः इनकार, अपरिवर्तनीय है। समस्या इन बाधाओं के तहत, सबसे बड़ी संभावना के साथ इनपुट अनुक्रम का एक विशिष्ट तत्व (उदाहरण के लिए सबसे बड़ा या सबसे छोटा मान) का चयन करना है। इस समस्या को [[ ऑड्स एल्गोरिथम ]] द्वारा हल किया जा सकता है, जो एक स्वतंत्रता की स्थिति के तहत इष्टतम उपज देता है; यह इनपुट की लंबाई में रैखिक होने वाली गणनाओं की संख्या के साथ एक एल्गोरिदम के रूप में भी इष्टतम है।
+वैकल्पिक रूप से चयन को स्वयं ऑनलाइन होने की आवश्यकता हो सकती है, अर्थात एक तत्व को केवल अनुक्रमिक इनपुट से अवलोकन के उदाहरण पर चुना जा सकता है। और प्रत्येक चयन, क्रमशः प्रतिषेध अपरिवर्तनीय है। समस्या इन बाधाओं के तहत सबसे बड़ी संभावना के साथ इनपुट अनुक्रम का एक विशिष्ट तत्व (उदाहरण के लिए सबसे बड़ा या सबसे छोटा मान) का चयन करना है। इस समस्या को  [[ ऑड्स एल्गोरिथम |ऑड्स एल्गोरिथम]]  द्वारा हल किया जा सकता है, जो स्वतंत्रता की स्थिति के तहत सर्वोत्तम उपज देता है। तथा यह एक एल्गोरिथम के रूप में भी सर्वोत्तम होती है, जिसमें इनपुट की लंबाई में गणनाओं की संख्या रैखिक होती है।
-सबसे सरल उदाहरण उच्च संभावना के साथ अधिकतम चुनने की [[ सचिव समस्या ]] है, इस मामले में इष्टतम रणनीति (यादृच्छिक डेटा पर) पहले n/e तत्वों के चल रहे अधिकतम को ट्रैक करना और उन्हें अस्वीकार करना है, और फिर पहले तत्व का चयन करना है इस अधिकतम से अधिक।
+सबसे सरल उदाहरण उच्च संभावना के साथ अधिकतम चुनने की  [[ सचिव समस्या |सचिव समस्या]]  है, इस स्थिति में सर्वोत्तम योजना यादृच्छिक डेटा पर पहले n/e तत्वों के चल रहे अधिकतम को ट्रैक करना और उन्हें अस्वीकार करना है, और फिर पहले तत्व का अधिकतम से अधिक चयन करना है।
 == संबंधित समस्याएं ==
-[[ श्रेणी प्रश्न ]]ों की समस्या उत्पन्न करते हुए, एक सूची के भीतर श्रेणियों पर लागू करने के लिए चयन समस्या का सामान्यीकरण किया जा सकता है। रेंज क्वेरीज़ # मेडियन (एकाधिक रेंज के माध्यकों की गणना) के प्रश्न का विश्लेषण किया गया है।
+एक सूची के अन्दर श्रेणियों पर लागू करने के लिए चयन समस्या को सामान्यीकृत कर सकता है, जिससे  [[ श्रेणी प्रश्न |श्रेणी प्रश्नों]]  की समस्या उत्पन्न हो सकती है। श्रेणी माध्यिका प्रश्नों (कई श्रेणियों के माध्यकों की गणना) के प्रश्न का विश्लेषण किया गया है।
 == भाषा समर्थन ==
-बहुत कम भाषाओं में सामान्य चयन के लिए अंतर्निहित समर्थन होता है, हालांकि कई सूची के सबसे छोटे या सबसे बड़े तत्व को खोजने की सुविधा प्रदान करते हैं। एक उल्लेखनीय अपवाद [[ C++ ]] है, जो एक टेम्पलेट प्रदान करता है <code>nth_element</code> अपेक्षित रैखिक समय की गारंटी के साथ विधि, और डेटा को विभाजित भी करता है, जिसके लिए आवश्यक है कि nth तत्व को उसके सही स्थान पर क्रमबद्ध किया जाए, nth तत्व से पहले के तत्व इससे कम हों, और nth तत्व के बाद के तत्व इससे अधिक हों। यह निहित है लेकिन आवश्यक नहीं है कि यह अपेक्षित रैखिक समय और डेटा के विभाजन की अपनी आवश्यकता के अनुसार होरे के एल्गोरिथ्म (या कुछ संस्करण) पर आधारित है।<ref>Section 25.3.2 of ISO/IEC 14882:2003(E) and 14882:1998(E)</ref><ref>[http://www.sgi.com/tech/stl/nth_element.html nth_element], SGI STL</ref>
+सामान्य चयन के लिए बहुत कम भाषाओं में अंतर्निहित समर्थन है, हालांकि कई सूची के सबसे छोटे या सबसे बड़े तत्व को खोजने की सुविधा प्रदान करते हैं। एक उल्लेखनीय अपवाद  [[ C++ |C++]] है, जो अपेक्षित रैखिक समय की गारंटी के साथ एक टेम्प्लेटेड <code>nth_element</code>  विधि प्रदान करता है, और डेटा को विभाजित भी करता है, जिसके लिए आवश्यक है कि nth तत्व को उसके सही स्थान पर क्रमबद्ध किया जाए, nth तत्व से पहले के तत्व इससे कम हैं, और तत्व nवें तत्व के बाद इससे अधिक हैं। यह निहित है लेकिन आवश्यक नहीं होता है, कि यह अपेक्षित रैखिक समय और डेटा के विभाजन की अपनी आवश्यकता के अनुसार होरे के एल्गोरिथ्म या कुछ संस्करण पर आधारित है।<ref>Section 25.3.2 of ISO/IEC 14882:2003(E) and 14882:1998(E)</ref><ref>[http://www.sgi.com/tech/stl/nth_element.html nth_element], SGI STL</ref>
-[[ पर्ल ]] के लिए, [[ सीपीएएन ]] से उपलब्ध मॉड्यूल [https://metacpan.org/module/Sort::Key::Top Sort::Key::Top], सूची से शीर्ष एन तत्वों का चयन करने के लिए कार्यों का एक सेट प्रदान करता है। कई ऑर्डरिंग और कस्टम कुंजी निष्कर्षण प्रक्रियाओं का उपयोग करना। इसके अलावा, [https://metacpan.org/module/Statistics::CaseResampling स्टैटिस्टिक्स::CaseResampling] मॉड्यूल शीघ्र चयन का उपयोग करके क्वांटाइल्स की गणना करने के लिए एक फ़ंक्शन प्रदान करता है।
-[[ पायथन (प्रोग्रामिंग भाषा) ]] की मानक लाइब्रेरी (2.4 के बाद से) में शामिल हैं <code>[https://docs.python.org/library/heapq.html heapq].nsmallest()</code> तथा <code>nlargest()</code>, ओ (एन लॉग के) समय में, क्रमबद्ध सूचियां लौटाना।<ref>{{Cite web|url=https://stackoverflow.com/a/23038826|title=Python - heapq.nlargest की समय जटिलता क्या है?}}</ref> नम्पी के पास है <code>partition()</code> समारोह।
+[[ पर्ल |पर्ल]]  के लिए, [[ सीपीएएन |सीपीएएन]]  से उपलब्ध प्रारूप   [https://metacpan.org/module/Sort::Key::Top Sort::Key::Top],  कई ऑर्डरिंग और कस्टम कुंजी निष्कर्षण प्रक्रियाओं का उपयोग करके सूची से शीर्ष एन तत्वों का चयन करने के लिए कार्यों का एक समुच्चय प्रदान करता है। इसके अतिरिक्त,  [https://metacpan.org/module/Statistics::CaseResampling सांख्यिकी::CaseResampling] मॉड्यूल शीघ्र चयन का उपयोग करके  विभाजक की गणना करने के लिए एक फलन प्रदान करता है।
-मैटलैब शामिल है <code>maxk()</code> तथा <code>mink()</code> फ़ंक्शंस, जो सदिश के साथ-साथ उनके सूचकांकों में अधिकतम (न्यूनतम) k मान लौटाते हैं।
+[[ पायथन (प्रोग्रामिंग भाषा) |पायथन (प्रोग्रामिंग भाषा)]] के मानक पुस्तकालय (2.4 के बाद से) में <code>[https://docs.python.org/library/heapq.html heapq].nsmallest()</code> तथा <code>nlargest()</code> सम्मिलित हैं, जो O(n log k) समय में वर्गीकृत की गई सूचियों को लौटाते हैं।<ref>{{Cite web|url=https://stackoverflow.com/a/23038826|title=Python - heapq.nlargest की समय जटिलता क्या है?}}</ref>  Numpy में <code>partition()</code> फलन है।
-क्योंकि छँटाई एल्गोरिथम # भाषा समर्थन अधिक सर्वव्यापी है, गति में कमी के बावजूद कई वातावरणों में अनुक्रमण के बाद छँटाई का सरलीकृत दृष्टिकोण पसंद किया जाता है। दरअसल, [[ आलसी मूल्यांकन ]] के लिए, यह सरलीकृत दृष्टिकोण k सबसे छोटी/सबसे बड़ी क्रमबद्ध (अधिकतम/न्यूनतम विशेष मामले के साथ) के लिए संभव सर्वोत्तम जटिलता भी प्राप्त कर सकता है यदि सॉर्ट पर्याप्त आलसी है{{Citation needed|date=April 2014}}.
+मैटलैब में <code>maxk()</code> और <code>mink()</code> फ़ंक्शन सम्मिलित हैं, जो सदिश के साथ-साथ उनके सूचकांकों में अधिकतम (न्यूनतम) k मान लौटाते हैं।
+चूँकि वर्गीकरण के लिए भाषा समर्थन अधिक सर्वव्यापी है, तथा गति में कमी के अतिरिक्त वर्गीकरण का सरलीकृत दृष्टिकोण जिसके बाद अनुक्रमण किया जाता है, कई वातावरणों में समान  किया जाता है। वास्तव में  [[ आलसी मूल्यांकन |अनुद्योगी मूल्यांकन]]  के लिए, यह सरलीकृत दृष्टिकोण k सबसे छोटी/सबसे बड़ी क्रमबद्ध (विशेष स्थिति के रूप में अधिकतम/न्यूनतम के साथ) के लिए संभव सर्वोत्तम जटिलता भी प्राप्त कर सकता है यदि क्रम पर्याप्त अनुद्योगी है। {{Citation needed|date=April 2014}}.
 == यह भी देखें ==
@@ Line 127: / Line 126: @@
 * "[http://www.ics.uci.edu/~eppstein/161/960125.html Lecture notes for January 25, 1996: Selection and order statistics]", ''ICS 161: Design and Analysis of Algorithms,'' David Eppstein
-{{DEFAULTSORT:Selection Algorithm}}[[Category:चयन एल्गोरिदम| ]]
+{{DEFAULTSORT:Selection Algorithm}}
-[[Category: Machine Translated Page]]
+[[Category:All articles lacking in-text citations|Selection Algorithm]]
-[[Category:Created On 14/11/2022]]
+[[Category:All articles to be expanded|Selection Algorithm]]
+[[Category:All articles with unsourced statements|Selection Algorithm]]
+[[Category:Articles lacking in-text citations from जुलाई 2017|Selection Algorithm]]
+[[Category:Articles to be expanded from जनवरी 2019|Selection Algorithm]]
+[[Category:Articles using small message boxes|Selection Algorithm]]
+[[Category:Articles with hatnote templates targeting a nonexistent page|Selection Algorithm]]
+[[Category:Articles with invalid date parameter in template|Selection Algorithm]]
+[[Category:Articles with short description|Selection Algorithm]]
+[[Category:Articles with unsourced statements from April 2014|Selection Algorithm]]
+[[Category:Articles with unsourced statements from April 2018|Selection Algorithm]]
+[[Category:Created On 14/11/2022|Selection Algorithm]]
+[[Category:Machine Translated Page|Selection Algorithm]]
+[[Category:Short description with empty Wikidata description|Selection Algorithm]]
+[[Category:चयन एल्गोरिदम| ]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 09:45, 25 November 2022

Contents

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

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

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

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

महत्वपूर्ण योजना के रूप में मध्यस्थ चयन

चयन द्वारा वृद्धिशील वर्गीकरण

उप-रेखीय समय में चयन करने के लिए डेटा संरचनाओं का उपयोग करना

निचली सीमा

अंतरिक्ष जटिलता

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

संबंधित समस्याएं

भाषा समर्थन

यह भी देखें

संदर्भ

ग्रन्थसूची

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 09:45, 25 November 2022

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

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

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

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

महत्वपूर्ण योजना के रूप में मध्यस्थ चयन

चयन द्वारा वृद्धिशील वर्गीकरण

उप-रेखीय समय में चयन करने के लिए डेटा संरचनाओं का उपयोग करना

निचली सीमा

अंतरिक्ष जटिलता

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

संबंधित समस्याएं

भाषा समर्थन

यह भी देखें

संदर्भ

ग्रन्थसूची

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories