क्विकसेलेक्ट

Quickselect

Animated visualization of the quickselect algorithm. Selecting the 22nd smallest value.
Class	Selection algorithm
Data structure	Array
Worst-case performance	$O$(n2)
Best-case performance	$O$(n)
Average performance	$O$(n)

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

क्विकसेलेक्ट क्विकॉर्ट के समान समग्र दृष्टिकोण का उपयोग करता है, एक तत्व को धुरी के रूप में चुनता है और धुरी के आधार पर डेटा को दो भागों में विभाजित करता है, तदनुसार धुरी से कम या अधिक। हालाँकि, क्विकसॉर्ट की तरह, दोनों तरफ पुनरावृत्ति करने के बजाय, क्विकसेलेक्ट केवल एक तरफ पुनरावृत्ति करता है - वह तत्व वाला पक्ष जिसे वह खोज रहा है। इससे औसत जटिलता कम हो जाती है $O(n\log n)$ को $O(n)$, की सबसे खराब स्थिति के साथ $O(n^{2})$.

क्विकॉर्ट की तरह, क्विकसेलेक्ट को आम तौर पर इन-प्लेस एल्गोरिदम के रूप में और चयन से परे लागू किया जाता है kवां तत्व, यह डेटा को आंशिक रूप से सॉर्ट भी करता है। सॉर्टिंग के साथ कनेक्शन की आगे की चर्चा के लिए चयन एल्गोरिदम देखें।

एल्गोरिदम

क्विकसॉर्ट में, एक उपप्रक्रिया होती है जिसे कहा जाता है partition जो, रैखिक समय में, एक सूची को समूहित कर सकता है (सूचकांकों से लेकर)। left को right) दो भागों में: वे जो एक निश्चित तत्व से छोटे हैं, और वे जो तत्व से बड़े या उसके बराबर हैं। यहां स्यूडोकोड है जो तत्व के बारे में एक विभाजन करता है list[pivotIndex]:

फ़ंक्शन विभाजन (सूची, बाएँ, दाएँ, पिवोटइंडेक्स) है
    पिवोटवैल्यू := सूची[पिवोटइंडेक्स]
    स्वैप सूची[पिवोटइंडेक्स] और सूची[दाएं] //पिवोट को अंत तक ले जाएं
    स्टोरइंडेक्स := बाएँ
    i के लिए बाएँ से दाएँ - 1 करो
        यदि सूची[i] <pivotValue तो
            स्वैप सूची[स्टोरइंडेक्स] और सूची[i]
            वेतन वृद्धि स्टोर इंडेक्स
    स्वैप सूची [दाएं] और सूची [स्टोर इंडेक्स] // धुरी को उसके अंतिम स्थान पर ले जाएं
    रिटर्न स्टोर इंडेक्स

इसे क्विकॉर्ट#लोमुटो विभाजन योजना के रूप में जाना जाता है, जो क्विकॉर्ट#होरे विभाजन योजना|होरे की मूल विभाजन योजना की तुलना में सरल लेकिन कम कुशल है।

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

// बाएँ..दाएँ सहित सूची का k-वाँ सबसे छोटा तत्व लौटाता है
// (अर्थात् बाएँ <= k <= दाएँ)।
'फ़ंक्शन' चुनें (सूची, बाएँ, दाएँ, k) 'है'
    'यदि' बाएँ = दाएँ 'तब' // यदि सूची में केवल एक तत्व है,
        'वापसी' सूची[बाएं] // उस तत्व को लौटाएं
    pivotIndex := ... // बाएँ और दाएँ के बीच एक pivotIndex चुनें,
                           // उदाहरण के लिए, बाएं + फर्श (रैंड() % (दाएं - बाएं + 1))
    पिवोटइंडेक्स := विभाजन (सूची, बाएँ, दाएँ, पिवोटइंडेक्स)
    // धुरी अपनी अंतिम क्रमबद्ध स्थिति में है
    'यदि' k = pivotIndex 'तब'
        'वापसी' सूची[के]
    'अन्यथा यदि' k < पिवोटइंडेक्स 'तब'
        'वापसी' चुनें (सूची, बाएँ, पिवोटइंडेक्स - 1, के)
    'अन्य'
        'वापसी' चयन करें (सूची, पिवोटइंडेक्स + 1, दाएँ, के)

---

क्विकॉर्ट से समानता पर ध्यान दें: जिस तरह न्यूनतम-आधारित चयन एल्गोरिथ्म एक आंशिक चयन सॉर्ट है, यह एक आंशिक क्विकॉर्ट है, जो केवल उत्पन्न और विभाजन करता है $O(\log n)$ उसके जैसा $O(n)$ विभाजन. इस सरल प्रक्रिया में रैखिक प्रदर्शन की उम्मीद है, और, क्विकसॉर्ट की तरह, व्यवहार में इसका प्रदर्शन काफी अच्छा है। यह एक इन-प्लेस एल्गोरिदम भी है, यदि पूंछ कॉल ऑप्टिमाइज़ेशन उपलब्ध है, या लूप के साथ पूँछ प्रत्यावर्तन को खत्म करने पर केवल निरंतर मेमोरी ओवरहेड की आवश्यकता होती है:

फ़ंक्शन चयन(सूची, बाएँ, दाएँ, k) है
    कुंडली
        यदि बाएँ = दाएँ तो
            वापसी सूची[बाएं]
        पिवोटइंडेक्स := ... // बाएँ और दाएँ के बीच पिवोटइंडेक्स चुनें
        पिवोटइंडेक्स := विभाजन (सूची, बाएँ, दाएँ, पिवोटइंडेक्स)
        यदि k = pivotIndex तो
            वापसी सूची[के]
        अन्यथा यदि k < pivotIndex तब
            दाएँ := पिवोटइंडेक्स − 1
        अन्य
            बाएँ := पिवोटइंडेक्स + 1

समय जटिलता

क्विकसॉर्ट की तरह, क्विकसेलेक्ट का औसत प्रदर्शन अच्छा है, लेकिन चुनी गई धुरी के प्रति संवेदनशील है। यदि अच्छे पिवोट्स चुने जाते हैं, यानी वे जो किसी दिए गए अंश द्वारा खोज सेट को लगातार कम करते हैं, तो खोज सेट आकार में तेजी से घटता है और प्रेरण (या ज्यामितीय श्रृंखला को संक्षेप में) से कोई देखता है कि प्रदर्शन रैखिक है, क्योंकि प्रत्येक चरण रैखिक है और कुल समय इसका एक स्थिर समय है (यह इस पर निर्भर करता है कि खोज सेट कितनी तेजी से कम होता है)। हालाँकि, यदि खराब पिवोट्स को लगातार चुना जाता है, जैसे कि हर बार केवल एक ही तत्व कम होना, तो सबसे खराब स्थिति का प्रदर्शन द्विघात होता है: $O(n^{2}).$ उदाहरण के लिए, किसी सेट के अधिकतम तत्व की खोज करने, पहले तत्व को धुरी के रूप में उपयोग करने और डेटा को क्रमबद्ध करने में ऐसा होता है। हालाँकि, बेतरतीब ढंग से चुने गए पिवोट्स के लिए, यह सबसे खराब स्थिति बहुत ही असंभावित है: से अधिक का उपयोग करने की संभावना $Cn$ किसी भी पर्याप्त बड़े स्थिरांक के लिए तुलना $C$, एक फ़ंक्शन के रूप में अतिघातीय रूप से छोटा है $C$.

वेरिएंट

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

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

औसत समय जटिलता की बेहतर गणना से सबसे खराब स्थिति उत्पन्न होती है $n(2+2\log 2+o(1))\leq 3.4n+o(n)$ यादृच्छिक पिवोट्स के लिए (माध्यिका के मामले में; अन्य k तेज़ हैं)। अधिक जटिल धुरी रणनीति द्वारा स्थिरांक को 3/2 तक सुधारा जा सकता है, जिससे फ्लॉयड-रिवेस्ट एल्गोरिथ्म प्राप्त होता है, जिसकी औसत जटिलता है $1.5n+O(n^{1/2})$ माध्यिका के लिए, अन्य k तेज़ होने के साथ।

यह भी देखें

• फ्लोयड-रिवेस्ट एल्गोरिदम
• अंतःचयन करें
• माध्यिकाओं का माध्यिका

बाहरी संबंध

• "qselect", Quickselect algorithm in Matlab, Manolis Lourakis