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

बिखरे, बिना क्रम वाले पत्थरों के बीच धूप से उभरा एक अंबर रंग का चिकना पत्थर।

पिवट के आधार पर मानों को बाँटकर, पूरी सूची को क्रमबद्ध किए बिना चुने हुए क्रम का मान ढूँढ़ें।

क्विकसिलेक्ट क्या है?

क्विकसिलेक्ट किसी बिना क्रम वाली सूची में चुने हुए क्रम स्थान का मान ढूँढ़ता है। इससे हम पूरी सूची को क्रमबद्ध किए बिना सबसे छोटा मान, मध्यिका या दसवाँ सबसे छोटा मान पा सकते हैं।

यह क्विक सॉर्ट की तरह पिवट चुनकर मानों का विभाजन करता है। लेकिन क्विकसिलेक्ट आगे केवल उसी हिस्से में काम करता है जिसमें उत्तर हो सकता है।

“चौथा सबसे छोटा” किसे कहते हैं?

क्रम स्थान गिनते समय सबसे छोटा मान पहला होता है। सूची 9, 2, 7, 4, 1, 8, 3 में चौथा सबसे छोटा मान 4 है, जबकि सूची स्वयं क्रमबद्ध नहीं है।

यदि प्रोग्राम स्थानों को शून्य से गिनता है, तो चौथा स्थान index तीन होगा। n मानों की सूची में kवाँ सबसे बड़ा मान पाने के लिए, जहाँ k की गिनती एक से शुरू होती है, शून्य-आधारित index n - k चुनें।

दोहराए गए मान कई क्रम स्थानों पर आ सकते हैं। चयन एल्गोरिद्म को यह स्पष्ट करना चाहिए कि एक ही मान कई स्थानों पर होने पर वह मान लौटाता है या कोई खास वस्तु। क्विकसिलेक्ट आम तौर पर चुने गए क्रम स्थान का मान लौटाता है।

क्विकसिलेक्ट कैसे काम करता है?

क्विकसिलेक्ट उन मानों की एक सीमा रखता है जिसमें अभी भी माँगा गया क्रम स्थान मौजूद है:

  1. मौजूदा सीमा में से एक पिवट चुनें।
  2. मानों को पिवट से छोटे, उसके बराबर और उससे बड़े हिस्सों में बाँटें।
  3. हर हिस्से में आने वाले क्रम स्थान गिनें।
  4. यदि माँगा गया क्रम स्थान बराबर वाले हिस्से में है, तो पिवट लौटाएँ।
  5. वरना उसी छोटे या बड़े हिस्से में आगे बढ़ें जिसमें माँगा गया स्थान है।

उदाहरण की सूची 9, 2, 7, 4, 1, 8, 3 लें और पिवट 4 चुनें। विभाजन के बाद छोटे मान 2, 1, 3, पिवट 4 और बड़े मान 9, 7, 8 होंगे। 4 से छोटे तीन मान हैं, इसलिए 4 चौथा सबसे छोटा मान है। दोनों हिस्सों को क्रमबद्ध करने की ज़रूरत नहीं।

कोई दूसरा पिवट उत्तर तुरंत न बताए। ऐसे में क्विकसिलेक्ट उस हिस्से को हटा देता है जिसमें माँगा गया क्रम स्थान नहीं हो सकता, और बाकी हिस्से पर प्रक्रिया दोहराता है।

एक सरल रूप

नीचे दिए गए छद्म-कोड में rank, k, शून्य-आधारित है। विभाजन less_end लौटाता है, जो पिवट से छोटा न होने वाले पहले मान का index है, और equal_end, जो पिवट के बराबर आख़िरी मान का index है।

quickselect(values, k)
    low = 0
    high = length(values) - 1

    while low <= high
        pivot = choose_random_value(values, low, high)
        (less_end, equal_end) =
            partition_into_less_equal_greater(values, low, high, pivot)

        if k < less_end
            high = less_end - 1
        else if k <= equal_end
            return values[k]
        else
            low = equal_end + 1

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

तीन उदाहरणों का अभ्यास करें

उदाहरण नियंत्रणों से तीन स्थितियों के बीच बदलें:

  • अलग-अलग मान: [9, 2, 7, 4, 1, 8, 3] में चौथा सबसे छोटा मान ढूँढ़ें। उत्तर 4 है।
  • मध्यिका: [9, 1, 6, 3, 8, 2, 7, 4, 5] का बीच वाला मान ढूँढ़ें। उत्तर 5 है।
  • दोहराए गए मान: [5, 2, 5, 1, 5, 3] में चौथा सबसे छोटा मान ढूँढ़ें। उत्तर 5 है; माँगा गया स्थान बराबर मानों के समूह में आता है।

हर उदाहरण के संदर्भ क्रम को चरण-दर-चरण देखें और समझें कि सक्रिय सीमा कैसे छोटी होती जाती है। अभ्यास क्षेत्र में अपनी सूची और क्रम स्थान डालें। विभाजन के फ़ैसले एक-एक करके लें, फिर अपने चरणों की तुलना संदर्भ क्रम से करें।

तुलना लोड हो रही है…

यह क्रमबद्ध करने से तेज़ क्यों है?

क्रमबद्ध करने में हर मान को सही जगह रखना पड़ता है। क्विकसिलेक्ट को केवल इतना काम करना होता है कि चुने गए क्रम स्थान का मान पहचाना जा सके।

विभाजन का एक चरण मौजूदा सीमा को एक बार देखता है। यदि पिवट यादृच्छिक रूप से चुना जाए, तो n मानों के लिए कुल काम का अपेक्षित समय O(n) होता है। फिर भी सबसे ख़राब स्थिति में समय O(n²) हो सकता है, यदि हर पिवट के बाद लगभग सभी मान सक्रिय सीमा में ही रह जाएँ।

सूची के भीतर ही काम करने वाला रूप, सूची के अतिरिक्त बहुत कम जगह लेता है। कुछ रूप recursion इस्तेमाल करते हैं, जिससे call stack के लिए जगह लगती है; क्रमिक रूप उस अतिरिक्त stack से बचता है।

क्विकसिलेक्ट कब उपयोगी है?

जब आपको क्रम स्थान के आधार पर कोई नतीजा चाहिए, पर पूरी सूची क्रमबद्ध नहीं करनी, तब क्विकसिलेक्ट उपयोगी है। उदाहरण के लिए:

  • मध्यिका या प्रतिशतक ढूँढ़ना
  • सबसे छोटे या सबसे बड़े k मान चुनना
  • आगे की गणना के लिए सीमा मान चुनना

यदि कई क्रम स्थान चाहिए या सभी मान क्रम में चाहिए, तो सूची को एक बार क्रमबद्ध करना सरल हो सकता है। क्विकसिलेक्ट मूल सूची का क्रम भी बदल सकता है, इसलिए मूल क्रम बचाना हो तो पहले उसकी प्रति बना लें।

मुख्य विचार क्या है?

क्विकसिलेक्ट केवल वहीं काम करता है जहाँ उत्तर अभी भी हो सकता है। पिवट सूची को हिस्सों में बाँटता है, और माँगा गया क्रम स्थान बताता है कि किस हिस्से को रखना है।

इसीलिए एक मान चुनने में पूरी सूची क्रमबद्ध करने से कम काम लग सकता है।

संदर्भ

एआई संबंधी खुलासा: यह लेख AI (ChatGPT) की सहायता से लिखा गया है। त्रुटियों और छूटी हुई बातों की ओर ध्यान दिलाने के लिए आपका स्वागत है।

Updated: 2026 Nov 18