मेरे पास यादृच्छिक पूर्णांक की एक सूची है। मैं सोच रहा हूं कि कौन सा एल्गोरिदम सूची :: सॉर्ट() विधि द्वारा उपयोग किया जाता है। जैसे निम्नलिखित कोड में:एसटीएल की सूची :: सॉर्ट() द्वारा किस सॉर्टिंग एल्गोरिदम का उपयोग किया जाता है?
list<int> mylist;
// ..insert a million values
mylist.sort();
संपादित करें: भी this more specific question देखें।
मानक को किसी विशेष एल्गोरिदम की आवश्यकता नहीं होती है, केवल यह स्थिर होना चाहिए, और यह लगभग एन एलजी एन तुलनाओं का उपयोग करके सॉर्ट को पूरा करता है। यह उदाहरण के लिए, एक मर्ज-सॉर्ट या त्वरित प्रकार के लिंक किए गए-सूची संस्करण की अनुमति देता है (लोकप्रिय धारणा के विपरीत, त्वरित क्रम आवश्यक अस्थिर है, भले ही सरणी के लिए सबसे आम कार्यान्वयन है)।
उस प्रावधान के साथ, संक्षिप्त उत्तर यह है कि वर्तमान मानक पुस्तकालयों में, std::sort को एक परिचय-क्रम (आत्मनिर्भर प्रकार) के रूप में कार्यान्वित किया जाता है, जो मूल रूप से एक क्विक्सोर्ट है जो इसकी रिकर्सन गहराई का ट्रैक रखता है, और एक पर स्विच करेगा हेपसोर्ट (आमतौर पर धीमी लेकिन गारंटीकृत ओ (एन लॉग एन) जटिलता) यदि क्विक्सॉर्ट रिकर्सन का बहुत गहराई से उपयोग कर रहा है। Introsort का हाल ही में हाल ही में आविष्कार किया गया था (1 99 0 के उत्तरार्ध में)। पुराने मानक पुस्तकालयों ने आम तौर पर इसके बजाय क्विक्सोर्ट का उपयोग किया।
stable_sort मौजूद है क्योंकि सरणी की तरह कंटेनर छँटाई के लिए, सबसे तेजी से छँटाई एल्गोरिदम का सबसे अस्थिर कर रहे हैं, तो मानक दोनों std::sort (तेज लेकिन जरूरी स्थिर नहीं) और std::stable_sort (स्थिर लेकिन अक्सर कुछ हद तक धीमी) भी शामिल है।
हालांकि, दोनों सामान्य रूप से यादृच्छिक-पहुंच इटरेटर्स की अपेक्षा करते हैं, और एक लिंक की गई सूची की तरह कुछ खराब (यदि बिल्कुल) काम करेंगे। लिंक्ड सूचियों के लिए सभ्य प्रदर्शन प्राप्त करने के लिए, मानक में list::sort शामिल है। एक लिंक्ड सूची के लिए, हालांकि, वास्तव में ऐसा कोई व्यापार-बंद नहीं है - यह एक मर्ज-सॉर्ट को लागू करना बहुत आसान है जो स्थिर और (लगभग) दोनों के रूप में तेज़ी से स्थिर है। इस प्रकार, उन्हें केवल sort सदस्य फ़ंक्शन की आवश्यकता होती है जो स्थिर होने की आवश्यकता होती है।
होगा तो क्यों एसटीएल में एक 'stable_sort' है? –
यह पूरी तरह कार्यान्वयन परिभाषित है। मानक के बारे में एकमात्र चीज यह कहती है कि यह जटिलता ओ (एन एलजी एन) है, और यह कि स्थिर है। यही है, समान तत्वों के सापेक्ष क्रम को क्रमबद्ध करने के बाद बदलने की गारंटी नहीं है।
std::list का सॉर्ट सदस्य फ़ंक्शन आम तौर पर मर्ज सॉर्ट के कुछ रूपों का उपयोग करके कार्यान्वित किया जाता है, क्योंकि विलय सॉर्ट स्थिर होता है, और जब आप लिंक की गई सूचियों के साथ काम कर रहे होते हैं तो विलय वास्तव में वास्तव में सस्ते होते हैं।
आशा में मदद करता है :)
आप शायद मतलब है कि * बराबर * तत्वों के सापेक्ष क्रम को क्रमबद्ध करने के बाद बदलने की गारंटी नहीं है। – meriton
यह सही है :) धन्यवाद। –
हालांकि यह कार्यान्वयन/विक्रेता निर्भर है, लेकिन सबसे कार्यान्वयन मैं जानता हूँ कि Introsort जिसका सबसे अच्छा & सबसे खराब स्थिति जटिलता है का उपयोग करता है ओ (nlogn)।
सूक्ष्म सूचियों का उपयोग सूचियों को क्रमबद्ध करने के लिए नहीं किया जाता है। –
मुझे लगता है एल्गोरिथ्म विक्रेता पर निर्भर है –