Median of medians दृष्टिकोण quicksort में विभाजित एल्गोरिदम में काफी लोकप्रिय पिवोट उत्पन्न करने के लिए बहुत लोकप्रिय है, जैसे कि यह समान रूप से सरणी को विभाजित करता है। इसका तर्क विकिपीडिया में दिया गया है:मेडियन एल्गोरिदम के औसत के स्पष्टीकरण
चयनित पिवट मध्यस्थों की सूची में तत्वों के आधे से भी कम है, जो एन/10 तत्वों (1/2 * (एन/5) के आसपास है)) प्रत्येक आधा के लिए। इनमें से प्रत्येक तत्व 5 का औसत है, जो इसे 2 अन्य तत्वों से कम करता है और ब्लॉक के बाहर 2 अन्य तत्वों से अधिक बनाता है। इसलिए, ब्लॉक ब्लॉक के बाहर 3 (एन/10) तत्वों से कम है, और ब्लॉक के बाहर एक और 3 (एन/10) तत्वों से अधिक है। इस प्रकार चुना गया औसत 30%/70% और 70%/30% के बीच तत्वों को विभाजित करता है, जो एल्गोरिदम के सबसे खराब-मामले रैखिक व्यवहार का आश्वासन देता है।
क्या कोई इसे मेरे लिए थोड़ा स्पष्ट रूप से समझा सकता है। मुझे तर्क समझना मुश्किल लगता है। संख्या के निम्नलिखित सेट की
बस एक और सवाल है, कैसे इस विधि गारंटी करता है कि यह संख्या मंझला हो जाएगा ? औसत एक संख्या है जो सरणी को ऊपरी और निचले हिस्से में विभाजित करता है। तो यह 30-30-70 आंकड़ा क्या इंगित करता है? – SexyBeast
ठीक है, मध्य मध्य में है, लेकिन 'एम' (उपरोक्त पाठ में) सभी संख्याओं का औसत नहीं है। यह केवल 1/5 संख्याओं का औसत है (जो स्वयं छोटे 5 तत्व समूहों के मध्य हैं)। अधिक ध्यान के साथ अंतिम अनुच्छेद पढ़ने का प्रयास करें। अंत में, जहां यह निष्कर्ष निकाला गया है कि 'एम' संख्याओं के कम से कम '3 एन/10' से बड़ा है, ठीक है कि' एम' में अनुवाद संख्याओं में से कम से कम 30% से बड़ा है।तो अंत में, यह 'एम' की तरह कम से कम 30% से बड़ा है और कम से कम 30% से छोटा है। 40% शेष है जिसे हम निश्चित नहीं हैं। – Shahbaz
फिर यह औसतन 50-50 विभाजन कैसे देता है? 50-50 विभाजन सामान्य औसत द्वारा दिया जाता है, है ना? – SexyBeast