c++ - विभिन्न एसटीएल कार्यान्वयन में सी++ 11 std:: क्रम में क्या एल्गोरिदम का उपयोग किया जाता है?




algorithm sorting (2)

सवाल यह है कि, एसटीएल कैसे कह सकता है std::sort सबसे खराब मामला ओ (एन लॉग (एन)) है , भले ही यह संक्षेप में एक क्विकॉर्ट है । एसटीएल का प्रकार IntroSort है । IntroSort संक्षेप में एक QuickSort है, अंतर पेश सबसे खराब मामला जटिलता बदल गया।

क्विकस्टोर्ट सबसे खराब मामला ओ (एन ^ 2) है

आप जो भी विभाजन चुनते हैं, वहां एक अनुक्रम मौजूद है कि क्विकस्टोर्ट ओ (एन ^ 2) पर चलेगा। आपके द्वारा चुने गए विभाजन में सबसे बुरी स्थिति होने की संभावना कम हो जाती है। ( यादृच्छिक पिवट चयन , मध्य-तीन-तीन, etc. )

संपादित करें: @ maxim1000 s सुधार के लिए धन्यवाद। पिवोट चयन एल्गोरिदम के साथ क्विक्सोर्ट मध्यस्थों के मध्य में ओ (एन लॉग (एन)) सबसे खराब मामला जटिलता है, लेकिन ओवरहेड के कारण यह परिचय देता है कि इसका अभ्यास अभ्यास में नहीं किया जाता है। यह दिखाता है कि कितना अच्छा चयन एल्गोरिदम, सैद्धांतिक रूप से पिवट चयन के माध्यम से सबसे बुरी स्थिति जटिलता को बदल सकता है।

IntroSort क्या करता है?

IntroSort QuickSort की शाखा को सीमित करता है। यह सबसे महत्वपूर्ण बात है, कि सीमा 2 * (लॉग एन) है । जब सीमा तक पहुंच जाती है, तो IntroSort किसी भी सॉर्टिंग एल्गोरिदम का उपयोग कर सकता है जिसमें ओ (एन लॉग (एन)) की सबसे खराब केस जटिलता है।

ब्रांचिंग बंद हो जाती है जब हमारे पास ओ (लॉग एन) सबप्रोबल्म्स होता है। हम हर subproblem ओ (एन लॉग एन) हल कर सकते हैं। (लोअर केस एन subproblem आकार के लिए खड़ा है)।

(एन लॉग एन) का योग अब हमारी सबसे खराब स्थिति जटिलता है।

क्विकॉर्ट के सबसे खराब मामले के लिए; मान लीजिए कि हमारे पास पहले से सॉर्ट किए गए सरणी हैं, और हम हमेशा इस सरणी में पिवोट के रूप में पहला तत्व चुनते हैं। प्रत्येक पुनरावृत्ति में हम केवल पहले तत्व से छुटकारा पा सकते हैं। अगर हम अंत तक इस तरह से चले गए, तो यह ओ (एन ^ 2) स्पष्ट रूप से होगा। IntroSort के साथ हम QuickSort को रोकते हैं, जब हम गहराई से लॉग (एन) तक पहुंचते हैं, तो हम शेष छोड़े गए सरणी के लिए हीपॉर्ट का उपयोग करते हैं।

16 -> 1  /**N**/
   \
    > 15 -> 1 /**N - 1**/
         \
          > 14 -> 1 /**N - 2**/
               \
                > 13 -> 1 /**N - log(N)**/  
                     \
                      > 12 /**(HeapSort Now) (N - log(N)) log (N - log(N))**/

उन्हें समझाओ;

ब्रांचिंग स्टॉप तक, N + (N - 1) + ... + (N - log(N)) ऑपरेशन किया जाता है। गॉस का योग करने के बजाय, हम बस N + (N - 1) + ... + (N - log(N)) < N log(N) कह सकते हैं।

हीपॉर्ट पार्ट है (N - log(N)) log(N - log(N)) < N log(N)

कुल मिलाकर जटिलता < 2 N log(N)

चूंकि स्थिरांक को छोड़ा जा सकता है, इसलिए IntroSort की सबसे खराब स्थिति जटिलता ओ (एन लॉग (एन)) है

जोड़ा गया जानकारी: जीसीसी एसटीएल कार्यान्वयन स्रोत कोड hereSort फ़ंक्शन लाइन 5461 पर है

सुधार: * माइक्रोसॉफ्ट .NET * सॉर्ट कार्यान्वयन 2012 से IntroSort है। संबंधित जानकारी here

सी ++ 11 मानक गारंटी देता है कि std::sort में सबसे खराब मामले में ओ (एन लॉगन) जटिलता है । यह सी ++ 98/03 में औसत-केस गारंटी से अलग है, जहां std::sort को क्विक्सोर्ट (शायद छोटे एन के लिए सम्मिलन प्रकार के साथ संयुक्त) के साथ कार्यान्वित किया जा सकता है, जिसमें ओ (एन ^ 2) सबसे खराब मामले में है (कुछ विशिष्ट इनपुट के लिए, जैसे क्रमबद्ध इनपुट)।

विभिन्न एसटीएल पुस्तकालयों में std::sort कार्यान्वयन में कोई बदलाव थे? अलग-अलग एसटीएल में सी ++ 11 का std::sort कार्यान्वित किया जाता है?


libstdc++ और libc++ लिए ऑनलाइन स्रोतों को ब्राउज़ करना, कोई यह देख सकता है कि दोनों पुस्तकालय एक परिचय-प्रकार मुख्य लूप से प्रसिद्ध सॉर्टिंग एल्गोरिदम के पूर्ण गैमट का उपयोग करते हैं:

std::sort , insertion_sort (एक O(N^2) एल्गोरिदम के लिए एक सहायक रूटीन है लेकिन इसे छोटे अनुक्रमों के लिए प्रतिस्पर्धी बनाने के लिए एक अच्छी स्केलिंग स्थिरता के साथ), साथ ही 0, 1 के उप-अनुक्रमों के लिए कुछ विशेष आवरण, 2, और 3 तत्व।

std::partial_sort , दोनों पुस्तकालय सामान्य रूप से heap_sort ( O(N log N) एक संस्करण का उपयोग करते हैं), क्योंकि उस विधि में एक अच्छा आविष्कार है कि यह एक क्रमबद्ध अनुवर्तीता रखता है (आमतौर पर इसे अधिक महंगा बनाने के लिए एक बड़ा स्केलिंग स्थिर होता है पूर्ण छंटनी के लिए)।

std::nth_element , std::nth_element (फिर एक ओ (एन ^ 2) एल्गोरिदम के लिए एक सहायक std::nth_element एक सहायक रूटीन है जो इसे छोटे अनुक्रमों के लिए प्रतिस्पर्धी बनाने के लिए)। नियमित सॉर्टिंग के लिए insertion_sort आमतौर पर nth_element पर हावी है, लेकिन nth_element के लिए सबसे छोटे तत्व होने का आविष्कार पूरी तरह से nth_element के व्यवहार से मेल खाता है।





stl