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