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

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]:

function partition (list, left, right, pivotIndex) is
 pivotValue := list[pivotIndex]
 swap list[pivotIndex] and list[right] // Move pivot to end
 storeIndex := left
 for i from left to right − 1 do
  if list[i] < pivotValue then
    swap list[storeIndex] and list[i]
   increment storeIndex
 swap list[right] and list[storeIndex] // Move pivot to its final place
 return storeIndex

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

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

// Returns the k-th smallest element of list within left..right inclusive
// (i.e. left <= k <= right).
function select(list, left, right, k) is
 if left = right then // If the list contains only one element,
  return list[left] // return that element
 pivotIndex := ...  // select a pivotIndex between left and right,
       // e.g., left + floor(rand() % (right − left + 1))
  pivotIndex := partition(list, left, right, pivotIndex)
 // The pivot is in its final sorted position
  if k = pivotIndex then
  return list[k]
 else if k < pivotIndex then
  return select(list, left, pivotIndex − 1, k)
 else
   return select(list, pivotIndex + 1, right, k)

---

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

function select(list, left, right, k) is
 loop
  if left = right then
   return list[left]
  pivotIndex := ...  // select pivotIndex between left and right
  pivotIndex := partition(list, left, right, pivotIndex)
  if k = pivotIndex then
   return list[k]
  else if k < pivotIndex then
   right := pivotIndex − 1
  else
   left := pivotIndex + 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