दो यादृच्छिक quicksort लागू करने के तरीकों,यादृच्छिक quicksort
Method1: एक यादृच्छिक धुरी का चयन
Method2: इनपुट के एक यादृच्छिक क्रमपरिवर्तन उत्पन्न कर रहा है और एक quicksort कि धुरी
के रूप में पहला तत्व चुनता करने के लिए इसे खिलायादृच्छिकरण के मामले में method2 विधि 2 जैसा ही है?
नोट: ऐसा लगता है कि Method2 सभी विभाजनों को समान रूप से संभव बनाता है लेकिन method1 नहीं करता है। तो यदि वे समान नहीं हैं, तो मैं समझना चाहता हूं कि प्रदर्शन प्रभाव क्या है।
हां। किसी भी मामले में, पिवट के रूप में चुने जाने वाले किसी भी विशेष तत्व की संभावना 1/लेन (इनपुट) है। (हालांकि, दूसरी विधि लगभग स्थिर कारक द्वारा निश्चित रूप से धीमी है, क्योंकि इसे यादृच्छिक क्रमपरिवर्तन उत्पन्न करने के लिए अतिरिक्त रैखिक पास की आवश्यकता होगी।)
लेकिन एक विशेष इनपुट के लिए, दूसरी विधि में सभी एन है! क्रमपरिवर्तन समान रूप से संभव है, लेकिन पहली विधि इनपुट के सापेक्ष क्रम को परिवर्तित नहीं करती है, इसलिए इसमें इनपुट के लिए सभी संभावित विभाजन शामिल नहीं होते हैं। तो मुझे लगता है कि एक अंतर है, लेकिन यह सुनिश्चित नहीं है कि इसका क्या असर होगा। –
मुझे यकीन नहीं है कि "सभी संभावित विभाजन" से आपका क्या मतलब है। पिवोट तत्व से अधिक या कम तत्वों का सेट उनके आदेश पर निर्भर नहीं है। – jacobm
मुझे खेद है कि मैं उलझन में आया, मैं अब समझ गया। धन्यवाद –
मैं हाँ कहूंगा। प्रत्येक चरण में बाइनरी विभाजन दोनों तरीकों से एक ही कानून का पालन करता है। –