Kth सबसे छोटे तत्व की खोज करें

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

निश्चित रूप से सभी को सरणी में k-th सबसे छोटे तत्व को खोजने के कार्य का सामना करना पड़ा। K-th तत्व की विशेषता है कि यह सरणी के तत्वों से अधिक (या बराबर) शेष तत्वों के Nk के बराबर या उससे कम है (जहाँ N सरणी में तत्वों की संख्या है)।

Kth सबसे छोटे तत्व को खोजने का कार्य आमतौर पर छँटाई समस्या से जुड़ा होता है, क्योंकि इस तत्व को खोजने की स्पष्ट विधि N तत्वों को क्रमबद्ध करना और kth को चुनना है।

लेकिन हम थोड़े अलग तरीके से जाएंगे। मुझे लगता है कि पाठकों को पता है कि त्वरित सॉर्ट एल्गोरिथ्म कैसे काम करता है, लेकिन सिर्फ मामले में, मैं आपको याद दिलाता हूं। एक यादृच्छिक तत्व x को सरणी में चुना जाता है, और तत्व को बाईं ओर स्कैन किया जाएगा जब तक कि तत्व [i]> x नहीं मिलता है, तब तक दाईं ओर स्कैन किया जाएगा जब तक कि तत्व [j] <x नहीं मिल जाता है। जैसे ही दो ऐसे तत्व मिलते हैं, उनका आदान-प्रदान किया जाता है और सूचकांकों तक स्कैनिंग जारी रहती है i, j सरणी के बीच में कहीं बराबर हो जाते हैं। परिणाम एक ऐसा सरणी है जिसके बाईं ओर में तत्व <= x होते हैं, और दाईं ओर तत्व> = x होते हैं। वर्णित प्रक्रिया को बाएं और दाएं पक्षों के लिए पुनरावर्ती रूप से लागू किया जाता है और तब तक जारी रहता है जब तक कि पूरी तरह से सॉर्ट किया गया सरणी प्राप्त नहीं हो जाता है। ( कुशल छँटाई एल्गोरिदम के बारे में थोड़ा अधिक )।

त्वरित छँटाई में उपयोग की जाने वाली पृथक्करण प्रक्रिया आपको वांछित (kth) तत्व को बहुत तेज़ी से खोजने की क्षमता देती है।
यह एल्गोरिथ्म निम्नानुसार काम करता है। पहले चरण में, एल = 1 और आर = एन के साथ पृथक्करण प्रक्रिया को कहा जाता है (अर्थात, पूरे सरणी के लिए पृथक्करण किया जाता है), और एक [के] को एक्स के पृथक्करण मान के रूप में चुना जाता है। अलग होने के बाद, सूचकांकों i, j के मान ऐसे प्राप्त होते हैं

एक [h] <x सभी h <i के लिए
एक [एच]> एक्स सभी एच> जे के लिए
मैं> जे

यहां तीन मामले संभव हैं:
• x का विभाजन मूल्य बहुत छोटा निकला। नतीजतन, दो भागों के बीच की सीमा कश्मीर के वांछित मूल्य से कम है। फिर पृथक्करण ऑपरेशन को तत्वों के साथ दोहराया जाना चाहिए [i] ... एक [R]।

• चयनित x मान बहुत बड़ा था। फिर जुदाई ऑपरेशन को तत्वों के साथ दोहराया जाना चाहिए [एल] ... एक [जे]।

• तत्व [k] आवश्यक अनुपात में दो भागों में सरणी को विभाजित करता है और इसलिए वांछित मूल्य है।


केस 3 का एहसास होने तक जुदाई ऑपरेशन को दोहराया जाना चाहिए। यह चक्र निम्नलिखित टुकड़े में व्यक्त किया गया है (मैं पास्कल के लिए माफी मांगता हूं, लेकिन अभी तक मेरे छात्रों को केवल यह पता है):

1. प्रक्रिया खोजें ( k : पूर्णांक ) ;
2. वर
3. एल , आर , आई , जे : पूर्णांक ;
4. डब्ल्यू , एक्स : पूर्णांक ;
5. शुरू करना
6. एल : = 1 ; आर : = एन ;
7. जबकि एल <आर - 1 करते हैं
8. शुरू करना
9. x : = [ ए ] ;
10. मैं : = एल ;
11. j : = R ;
12. दोहराएं
13. जबकि एक [ i ] <x करते हैं
14. i : = i + 1 ;
15. जबकि x < [ j ] करते हैं
16. j : = j - 1 ;
17. अगर मैं < = j तब
18. शुरू करना
19. w : = एक [ i ] ;
20. एक [ i ] : = एक [ जे ] ;
21. एक [ जे ] : = डब्ल्यू ;
22. i : = i + 1 ;
23. j : = j - 1 ;
24. अंत ;
25. UNTIL i> j ;
26. अगर j <k
27. एल : = मैं ;
28. अगर k <i
29. आर : = जे ;
30. अंत ;
31. अंत ;

यदि हम मानते हैं कि औसतन प्रत्येक विभाजन सरणी के उस भाग के आकार को द्विभाजित करता है जिसमें वांछित मूल्य स्थित है, तो तुलना की आवश्यक संख्या N + N / 2 + N / 4 + ... + 1 = 2N होगी। यह मध्यस्थों और अन्य मात्राओं को खोजने के लिए उपरोक्त प्रक्रिया की प्रभावशीलता की व्याख्या करता है, और सरल विधि पर इसकी श्रेष्ठता भी बताता है, जिसमें पहले तत्व को छांटना होता है जिसमें बाद में kth तत्व का चयन होता है (जहां सबसे अच्छा व्यवहार N * log (N) के क्रम का होता है)।

मुझे आशा है कि यह एल्गोरिथ्म आपके कार्यक्रमों को अधिक कुशल और तेज़ बनाने में आपकी मदद करता है। आपका ध्यान देने के लिए धन्यवाद।