c++ - आधुनिक सी++ में क्लासिक सॉर्टिंग एल्गोरिदम को कैसे कार्यान्वित करें?




algorithm sorting (2)

सी ++ मानक लाइब्रेरी से std::sort algorithm (और उसके चचेरे भाई std::partial_sort और std::nth_element ) अधिकांश कार्यान्वयन में अधिक प्राथमिक सॉर्टिंग एल्गोरिदम का एक जटिल और संकर समामेलन है , जैसे कि चयन क्रम , सम्मिलन क्रम , त्वरित प्रकार , सॉर्ट, या ढेर प्रकार मर्ज करें।

यहां कई प्रश्न हैं और बहन साइट्स जैसे https://codereview.stackexchange.com/ इन क्लासिक सॉर्टिंग एल्गोरिदम के कार्यान्वयन के बग, जटिलता और अन्य पहलुओं से संबंधित हैं। प्रस्तावित अधिकांश कार्यान्वयन में कच्चे लूप होते हैं, इंडेक्स मैनिपुलेशन और कंक्रीट प्रकार का उपयोग करते हैं, और आमतौर पर शुद्धता और दक्षता के मामले में विश्लेषण करने के लिए गैर-तुच्छ होते हैं।

प्रश्न : उपरोक्त वर्णित क्लासिक सॉर्टिंग एल्गोरिदम आधुनिक सी ++ का उपयोग करके कैसे कार्यान्वित किया जा सकता है?

  • कोई कच्चा लूप नहीं , लेकिन <algorithm> से मानक लाइब्रेरी के एल्गोरिदमिक बिल्डिंग ब्लॉक का संयोजन
  • इटरेटर इंटरफ़ेस और इंडेक्स हेरफेर और कंक्रीट प्रकारों के बजाय टेम्पलेट्स का उपयोग
  • सी ++ 14 शैली , जिसमें पूर्ण मानक लाइब्रेरी, साथ ही सिंटैक्टिक शोर रेड्यूसर जैसे auto , टेम्पलेट एलियास, पारदर्शी तुलनित्र और पॉलिमॉर्फिक लैम्बडा शामिल हैं।

नोट्स :

  • सॉर्टिंग एल्गोरिदम के कार्यान्वयन पर और संदर्भों के लिए Wikipedia , रोसेटा कोड या http://www.sorting-algorithms.com/
  • शॉन पेरेंट के सम्मेलनों (स्लाइड 39) के अनुसार, एक कच्चा पाश एक ऑपरेटर के साथ दो कार्यों की संरचना से अधिक लंबा है। तो f(g(x)); या f(x); g(x); f(x); g(x); या f(x) + g(x); कच्चे लूप नहीं हैं, और न ही select_sort और insertion_sort में लूप हैं।
  • मैं मौजूदा सी ++ 1y को पहले से ही सी ++ 14 के रूप में इंगित करने के लिए स्कॉट मेयर्स की शब्दावली का पालन करता हूं, और सी ++ 98 और सी ++ 03 दोनों को सी ++ 98 के रूप में इंगित करने के लिए, इसलिए इसके लिए मुझे दोष न दें।
  • जैसा कि @ मेहरदाद द्वारा टिप्पणियों में सुझाव दिया गया है, मैं उत्तर के अंत में एक लाइव उदाहरण के रूप में चार कार्यान्वयन प्रदान करता हूं: सी ++ 14, सी ++ 11, सी ++ 98 और बूस्ट और सी ++ 98।
  • उत्तर स्वयं केवल सी ++ 14 के संदर्भ में प्रस्तुत किया जाता है। जहां प्रासंगिक है, मैं वाक्य रचनात्मक और पुस्तकालय मतभेदों को इंगित करता हूं जहां विभिन्न भाषा संस्करण भिन्न होते हैं।

एल्गोरिदमिक बिल्डिंग ब्लॉक

हम मानक पुस्तकालय से एल्गोरिदमिक बिल्डिंग ब्लॉक को इकट्ठा करके शुरू करते हैं:

#include <algorithm>    // min_element, iter_swap, 
                        // upper_bound, rotate, 
                        // partition, 
                        // inplace_merge,
                        // make_heap, sort_heap, push_heap, pop_heap,
                        // is_heap, is_sorted
#include <cassert>      // assert 
#include <functional>   // less
#include <iterator>     // distance, begin, end, next
  • इटेटरेटर टूल जैसे कि गैर-सदस्य std::begin() / std::end() साथ-साथ std::next() के साथ ही सी ++ 11 और उसके बाद के संस्करण के रूप में उपलब्ध हैं। सी ++ 98 के लिए, इन्हें स्वयं लिखना होगा। boost::begin() से विकल्प हैं। बूस्ट में रेंज boost::begin() / boost::end() , और बूस्ट से। boost::next() उपयोग में क्षमता boost::next()
  • std::is_sorted एल्गोरिदम केवल C ++ 11 और उससे आगे के लिए उपलब्ध है। सी ++ 98 के लिए, इसे std::adjacent_find और एक हाथ से लिखित फ़ंक्शन ऑब्जेक्ट के संदर्भ में कार्यान्वित किया जा सकता है। बूस्ट। boost::algorithm::is_sorted भी एक boost::algorithm::is_sorted एक विकल्प के रूप में प्रदान करता है।
  • std::is_heap एल्गोरिदम केवल C ++ 11 और उससे आगे के लिए उपलब्ध है।

Syntactical उपहार

सी ++ 14 फॉर्म के पारदर्शी तुलनित्र प्रदान करता है std::less<> जो उनके तर्कों पर बहुलक रूप से कार्य करता है। यह एक इटरेटर के प्रकार प्रदान करने से बचाता है। इसका उपयोग C ++ 11 के डिफ़ॉल्ट फ़ंक्शन टेम्पलेट तर्कों के साथ संयोजन में किया जा सकता है ताकि एल्गोरिदम को सॉर्ट करने के लिए एक ओवरलोड लोड किया जा सके जो तुलनात्मक रूप से < और उपयोगकर्ता द्वारा परिभाषित तुलना फ़ंक्शन ऑब्जेक्ट है।

template<class It, class Compare = std::less<>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

सी ++ 11 में, कोई एक पुनरावर्तनीय टेम्पलेट उपनाम को एक इटरेटर के मान प्रकार को निकालने के लिए परिभाषित कर सकता है जो क्रमशः एल्गोरिदम के हस्ताक्षर के लिए मामूली अव्यवस्था जोड़ता है:

template<class It>
using value_type_t = typename std::iterator_traits<It>::value_type;

template<class It, class Compare = std::less<value_type_t<It>>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

सी ++ 98 में, किसी को दो ओवरलोड लिखने की आवश्यकता होती है और वर्बोज़ typename xxx<yyy>::type सिंटैक्स का उपयोग करने की आवश्यकता होती है

template<class It, class Compare>
void xxx_sort(It first, It last, Compare cmp); // general implementation

template<class It>
void xxx_sort(It first, It last)
{
    xxx_sort(first, last, std::less<typename std::iterator_traits<It>::value_type>());
}
  • एक अन्य वाक्य रचनात्मक निस्संदेह यह है कि सी ++ 14 पॉलिमॉर्फिक लैम्ब्डास के माध्यम से उपयोगकर्ता परिभाषित तुलनाकर्ताओं को लपेटने की सुविधा प्रदान करता है ( auto पैरामीटर के साथ जो फ़ंक्शन टेम्पलेट तर्कों की तरह घटाए जाते हैं)।
  • सी ++ 11 में केवल मोनोमोर्फिक लैम्बडास है, जिसके लिए उपरोक्त टेम्पलेट उपनाम value_type_t के उपयोग की आवश्यकता होती है।
  • सी ++ 98 में, किसी को या तो एक स्टैंडअलोन फ़ंक्शन ऑब्जेक्ट लिखना होगा या वर्बोज़ std::bind1st / std::bind2nd / std::not1 सिंटैक्स प्रकार का std::not1
  • Boost.Bind boost::bind और _1 / _2 प्लेसहोल्डर सिंटैक्स के साथ इसे बेहतर बनाता है।
  • सी ++ 11 और उसके बाद भी std::find_if_not , जबकि C ++ 98 को std::find_if आवश्यकता std::not1 जो एक फ़ंक्शन ऑब्जेक्ट के चारों ओर std::not1 साथ होती है।

सी ++ शैली

अभी तक कोई आम तौर पर स्वीकार्य सी ++ 14 शैली नहीं है। बदतर के लिए बेहतर, मैं स्कॉट मेयर्स के ड्राफ्ट इफेक्टिव मॉडर्न सी ++ और हर्ब सटर के संशोधित गॉटड का बारीकी से पालन करता हूं । मैं निम्नलिखित शैली की सिफारिशों का उपयोग करता हूं:

  • हर्ब सटर की "लगभग हमेशा ऑटो" और स्कॉट मेयर्स की "विशिष्ट प्रकार की घोषणाओं के लिए ऑटो पसंदीदा" सिफारिश, जिसके लिए ब्रेवटी गुम हो गई है, हालांकि इसकी स्पष्टता कभी-कभी disputed
  • स्कॉट मेयर्स की "ऑब्जेक्ट्स बनाते समय () और {} ऑब्जेक्ट्स बनाते हैं" और लगातार पुरानी ब्रांडेड प्रारंभिकरण () बजाय ब्रेसिड-प्रारंभिक {} चयन करें () जेनेरिक कोड में सभी सर्वाधिक-वेक्सिंग-पार्स मुद्दों को साइड-स्टेप करने के लिए)।
  • स्कॉट मेयर्स की "टाइपीफ्स को उपनाम घोषित करना" । टेम्पलेट्स के लिए यह वैसे भी जरूरी है, और typedef बजाय हर जगह इसका उपयोग समय बचाता है और स्थिरता जोड़ता है।
  • मैं पहले से क्रमबद्ध उप-श्रेणियों के लिए लूप इनवेरिएंट जांच की अनुमति देने के लिए, कुछ स्थानों पर पैटर्न for (auto it = first; it != last; ++it) पैटर्न का उपयोग करता हूं। उत्पादन कोड में, लूप के अंदर कहीं while (first != last) और एक ++first उपयोग थोड़ा बेहतर हो सकता है।

चयन छांटना

चयन क्रम किसी भी तरह से डेटा को अनुकूलित नहीं करता है, इसलिए इसका रनटाइम हमेशा O(N^2) । हालांकि, चयन प्रकार में स्वैप की संख्या को कम करने की संपत्ति है। उन अनुप्रयोगों में जहां स्वैपिंग आइटम की लागत अधिक है, चयन क्रम बहुत अच्छी तरह से पसंद का एल्गोरिदम हो सकता है।

मानक लाइब्रेरी का उपयोग करके इसे कार्यान्वित करने के लिए, शेष न्यूनतम तत्व खोजने के लिए बार-बार std::min_element का उपयोग करें, और iter_swap को इसे iter_swap करने के लिए:

template<class FwdIt, class Compare = std::less<>>
void selection_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const selection = std::min_element(it, last, cmp);
        std::iter_swap(selection, it); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

ध्यान दें कि selection_sort में पहले से संसाधित रेंज है [first, it) इसके लूप इनवेरिएंट के रूप में क्रमबद्ध किया गया है। std::sort के यादृच्छिक अभिगम इटरेटर्स की तुलना में न्यूनतम आवश्यकताएं इटरेटर हैं।

विवरण छोड़ा गया :

  • चयन प्रकार को प्रारंभिक परीक्षण के साथ अनुकूलित किया जा सकता है if (std::distance(first, last) <= 1) return; (या आगे / बिडरेक्शनल इटरेटर के लिए: if (first == last || std::next(first) == last) return; )।
  • बिडरेक्शनल इटरेटर्स के लिए , उपरोक्त परीक्षण अंतराल पर एक लूप के साथ जोड़ा जा सकता है [first, std::prev(last)) , क्योंकि अंतिम तत्व न्यूनतम शेष तत्व होने की गारंटी है और उसे स्वैप की आवश्यकता नहीं है।

सम्मिलन सॉर्ट

हालांकि यह O(N^2) सबसे खराब-केस समय के साथ प्राथमिक सॉर्टिंग एल्गोरिदम में से एक है, प्रविष्टि क्रम पसंद के एल्गोरिदम है या तो जब डेटा लगभग सॉर्ट किया जाता है (क्योंकि यह अनुकूली है ) या जब समस्या का आकार छोटा होता है (क्योंकि यह कम ओवरहेड है)। इन कारणों से, और क्योंकि यह भी स्थिर है , सम्मिलन क्रम अक्सर उच्च ओवरहेड विभाजित करने के लिए रिकर्सिव बेस केस (जब समस्या का आकार छोटा होता है) के रूप में उपयोग किया जाता है और सॉर्टिंग एल्गोरिदम को हल करता है, जैसे मर्ज सॉर्ट या त्वरित सॉर्ट।

मानक लाइब्रेरी के साथ insertion_sort को कार्यान्वित करने के लिए, उस स्थान को ढूंढने के लिए बार-बार std::upper_bound का उपयोग करें जहां वर्तमान तत्व को जाना है, और शेष तत्वों को इनपुट रेंज में ऊपर की ओर स्थानांतरित करने के लिए std::rotate का उपयोग करें:

template<class FwdIt, class Compare = std::less<>>
void insertion_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const insertion = std::upper_bound(first, it, *it, cmp);
        std::rotate(insertion, it, std::next(it)); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

ध्यान दें कि insertion_sort में पहले से संसाधित सीमा है [first, it) इसके लूप इनवेरिएंट के रूप में क्रमबद्ध किया गया है। सम्मिलन क्रम भी आगे इटरेटर के साथ काम करता है।

विवरण छोड़ा गया :

  • सम्मिलन प्रकार को प्रारंभिक परीक्षण के साथ अनुकूलित किया जा सकता है if (std::distance(first, last) <= 1) return; (या आगे / बिडरेक्शनल इटरेटर के लिए: if (first == last || std::next(first) == last) return; ) और अंतराल पर एक लूप [std::next(first), last) , क्योंकि पहले तत्व को जगह में होने की गारंटी है और घूर्णन की आवश्यकता नहीं है।
  • std::find_if_not लिए, सम्मिलन बिंदु खोजने के लिए बाइनरी खोज को मानक लाइब्रेरी के std::find_if_not एल्गोरिदम का उपयोग करके एक विपरीत रैखिक खोज के साथ प्रतिस्थापित किया जा सकता है।

नीचे दिए गए टुकड़े के लिए चार लाइव उदाहरण ( C++14 , C++11 , सी ++ 98 और बूस्ट , C++98 )

using RevIt = std::reverse_iterator<BiDirIt>;
auto const insertion = std::find_if_not(RevIt(it), RevIt(first), 
    [=](auto const& elem){ return cmp(*it, elem); }
).base();
  • यादृच्छिक इनपुट के लिए यह O(N^2) तुलना देता है, लेकिन यह लगभग क्रमबद्ध इनपुट के लिए O(N) तुलना में सुधार करता है। द्विआधारी खोज हमेशा O(N log N) तुलना का उपयोग करती है।
  • छोटी इनपुट श्रेणियों के लिए, एक रैखिक खोज की बेहतर मेमोरी इलाके (कैश, प्रीफेचिंग) भी बाइनरी खोज पर हावी हो सकती है (किसी को इसका परीक्षण करना चाहिए)।

जल्दी से सुलझाएं

सावधानीपूर्वक कार्यान्वित होने पर, त्वरित क्रम मजबूत होता है और O(N log N) अपेक्षित जटिलता है, लेकिन O(N^2) सबसे खराब-मामले जटिलता के साथ जिसे प्रतिकूल रूप से चुने गए इनपुट डेटा के साथ ट्रिगर किया जा सकता है। जब एक स्थिर प्रकार की आवश्यकता नहीं होती है, तो त्वरित क्रम एक उत्कृष्ट सामान्य उद्देश्य का प्रकार होता है।

यहां तक ​​कि सबसे सरल संस्करणों के लिए, अन्य क्लासिक सॉर्टिंग एल्गोरिदम की तुलना में मानक लाइब्रेरी का उपयोग करके कार्यान्वित करने के लिए त्वरित प्रकार थोड़ा जटिल है। नीचे दिया गया दृष्टिकोण इनपुट रेंज के मध्य तत्व [first, last) को पिवट के रूप में ढूंढने के लिए कुछ पुनरावर्तक उपयोगिताओं का उपयोग करता है, फिर std::partition (जो O(N) ) में दो कॉल का उपयोग तीन-तरफा विभाजन इनपुट में करें उन तत्वों के खंडों में रेंज करें जो क्रमशः चयनित पिवट से छोटे, बराबर, और बड़े होते हैं। अंत में पिवट की तुलना में छोटे और बड़े तत्वों के साथ दो बाहरी खंडों को क्रमबद्ध रूप से क्रमबद्ध किया जाता है:

template<class FwdIt, class Compare = std::less<>>
void quick_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;
    auto const pivot = *std::next(first, N / 2);
    auto const middle1 = std::partition(first, last, [=](auto const& elem){ 
        return cmp(elem, pivot); 
    });
    auto const middle2 = std::partition(middle1, last, [=](auto const& elem){ 
        return !cmp(pivot, elem);
    });
    quick_sort(first, middle1, cmp); // assert(std::is_sorted(first, middle1, cmp));
    quick_sort(middle2, last, cmp);  // assert(std::is_sorted(middle2, last, cmp));
}

हालांकि, त्वरित और कुशल होने के लिए त्वरित प्रकार कठिन है, क्योंकि उपर्युक्त चरणों में से प्रत्येक को सावधानीपूर्वक जांच और उत्पादन स्तर कोड के लिए अनुकूलित किया जाना चाहिए। विशेष रूप से, O(N log N) जटिलता के लिए, पिवट को इनपुट डेटा के संतुलित विभाजन में परिणाम देना होता है, जिसे O(1) पिवट के लिए सामान्य रूप से गारंटी नहीं दी जा सकती है, लेकिन अगर कोई पिवट सेट करता है तो इसकी गारंटी दी जा सकती है इनपुट रेंज के O(N) औसत के रूप में।

विवरण छोड़ा गया :

  • उपर्युक्त कार्यान्वयन विशेष रूप से विशेष इनपुट के लिए कमजोर है, उदाहरण के लिए " अंग पाइप " इनपुट 1, 2, 3, ..., N/2, ... 3, 2, 1 (के लिए O(N^2) जटिलता है क्योंकि मध्य हमेशा अन्य सभी तत्वों से बड़ा होता है)।
  • लगभग क्रमबद्ध इनपुट के खिलाफ इनपुट रेंज गार्ड से यादृच्छिक रूप से चुने गए तत्वों से median-of-3 पिवट चयन, जिसके लिए जटिलता अन्यथा O(N^2) बिगड़ती है।
  • 3-तरफा विभाजन (pivot से बराबर और बड़े तत्वों को अलग करना) जैसा कि std::partition को दो कॉलों द्वारा दिखाया गया है, इस परिणाम को प्राप्त करने के लिए सबसे कुशल O(N) एल्गोरिदम नहीं है।
  • यादृच्छिक अभिगम इटरेटर्स के लिए , एक गारंटीकृत O(N log N) जटिलता std::nth_element(first, middle, last) का उपयोग करके औसत पिवट चयन के माध्यम से हासिल की जा सकती है, इसके बाद रिकर्सिव कॉल को quick_sort(first, middle, cmp) और quick_sort(middle, last, cmp)
  • यह गारंटी लागत पर आती है, हालांकि, क्योंकि std::nth_element की O(N) जटिलता का निरंतर कारक मध्यस्थ -3 पिवट की O(1) जटिलता की तुलना में अधिक महंगा हो सकता है, उसके बाद O(N) std::partition को कॉल करें (जो डेटा पर एक कैश-अनुकूल सिंगल फॉरवर्ड पास है)।

मर्ज़ सॉर्ट

यदि O(N) अतिरिक्त स्थान का उपयोग करना कोई चिंता नहीं है, तो सॉर्ट मर्ज करना एक उत्कृष्ट विकल्प है: यह एकमात्र स्थिर O(N log N) सॉर्टिंग एल्गोरिदम है।

मानक एल्गोरिदम का उपयोग करके कार्यान्वित करना आसान है: इनपुट रेंज के बीच का पता लगाने के लिए कुछ इटरेटर उपयोगिताओं का उपयोग करें [first, last) और एक std::inplace_merge साथ दो पुनरावर्ती क्रमबद्ध सेगमेंट को गठबंधन करें:

template<class BiDirIt, class Compare = std::less<>>
void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;                   
    auto const middle = std::next(first, N / 2);
    merge_sort(first, middle, cmp); // assert(std::is_sorted(first, middle, cmp));
    merge_sort(middle, last, cmp);  // assert(std::is_sorted(middle, last, cmp));
    std::inplace_merge(first, middle, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

मर्ज सॉर्ट को std::inplace_merge आवश्यकता होती है, बाधा std::inplace_merge । ध्यान दें कि लिंक की गई सूचियों को सॉर्ट करते समय, मर्ज सॉर्ट केवल O(log N) अतिरिक्त स्थान (रिकर्सन के लिए) की आवश्यकता होती है। बाद वाला एल्गोरिदम मानक पुस्तकालय में std::list<T>::sort द्वारा कार्यान्वित किया गया है।

ढेर बनाएं और छांटें

हीप सॉर्ट लागू करने के लिए सरल है, O(N log N) इन-प्लेस सॉर्ट करता है, लेकिन स्थिर नहीं है।

पहला लूप, O(N) "हेपफाइफा" चरण, सरणी को ढेर क्रम में रखता है। दूसरा लूप, O(N log N ) "सॉर्टडाउन" चरण, बार-बार अधिकतम निकाल देता है और हीप ऑर्डर को पुनर्स्थापित करता है। मानक पुस्तकालय यह बेहद सरल बनाता है:

template<class RandomIt, class Compare = std::less<>>
void heap_sort(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    lib::make_heap(first, last, cmp); // assert(std::is_heap(first, last, cmp));
    lib::sort_heap(first, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

यदि आप इसे std::make_heap और std::sort_heap का उपयोग करने के लिए "धोखाधड़ी" std::sort_heap , तो आप क्रमशः std::push_heap और std::pop_heap संदर्भ में एक स्तर को गहराई से लिख सकते हैं और उन कार्यों को स्वयं लिख सकते हैं:

namespace lib {

// NOTE: is O(N log N), not O(N) as std::make_heap
template<class RandomIt, class Compare = std::less<>>
void make_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last;) {
        std::push_heap(first, ++it, cmp); 
        assert(std::is_heap(first, it, cmp));           
    }
}

template<class RandomIt, class Compare = std::less<>>
void sort_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = last; it != first;) {
        std::pop_heap(first, it--, cmp);
        assert(std::is_heap(first, it, cmp));           
    } 
}

}   // namespace lib

मानक लाइब्रेरी push_heap और pop_heap दोनों जटिलता O(log N) रूप में निर्दिष्ट करती है। ध्यान दें कि रेंज [first, last) बाहरी [first, last) श्रेणी में बाहरी लूप make_heap लिए O(N log N) जटिलता में परिणाम देता है, जबकि std::make_heap में केवल O(N) जटिलता है। heap_sort की कुल O(N log N) जटिलता के लिए इससे कोई फर्क नहीं पड़ता।

विवरण छोड़ा गया : O(N) make_heap कार्यान्वयन

परिक्षण

यहां चार लाइव उदाहरण ( C++14 , C++11 , सी ++ 98 और बूस्ट , C++98 ) विभिन्न इनपुट पर सभी पांच एल्गोरिदम का परीक्षण कर रहे हैं (पूर्ण या कठोर होने के लिए नहीं)। बस एलओसी में भारी मतभेदों को ध्यान दें: सी ++ 11 / सी ++ 14 को लगभग 130 एलओसी, सी ++ 98 और बूस्ट 190 (+ 50%) और सी ++ 98 270 (+ 100%) से अधिक की आवश्यकता है।


एक और छोटा और बल्कि सुरुचिपूर्ण मूल रूप से कोड समीक्षा पर पाया गया । मैंने सोचा कि यह साझा करने लायक था।

गिनती क्रमबद्ध करें

हालांकि यह विशेष रूप से विशिष्ट है, गिनती क्रम एक साधारण पूर्णांक सॉर्टिंग एल्गोरिदम है और अक्सर वास्तव में तेज़ हो सकता है बशर्ते कि पूर्णांक के मानों को क्रमबद्ध करने के लिए बहुत दूर न हों। यह शायद आदर्श है यदि किसी को कभी भी एक लाख पूर्णांक संग्रह को सॉर्ट करने की आवश्यकता होती है जिसे उदाहरण के लिए 0 और 100 के बीच जाना जाता है।

एक बहुत ही सरल गणना प्रकार को लागू करने के लिए जो हस्ताक्षरित और हस्ताक्षरित पूर्णांक दोनों के साथ काम करता है, किसी को संग्रह में छोटे और सबसे बड़े तत्वों को क्रमबद्ध करने की आवश्यकता होती है; उनका अंतर आवंटित करने के लिए गणना की सरणी के आकार को बताएगा। फिर, संग्रह के माध्यम से एक दूसरा पास प्रत्येक तत्व की घटनाओं की संख्या को गिनने के लिए किया जाता है। अंत में, हम मूल संग्रह में वापस प्रत्येक पूर्णांक की आवश्यक संख्या वापस लिखते हैं।

template<typename ForwardIterator>
void counting_sort(ForwardIterator first, ForwardIterator last)
{
    if (first == last || std::next(first) == last) return;

    auto minmax = std::minmax_element(first, last);  // avoid if possible.
    auto min = *minmax.first;
    auto max = *minmax.second;
    if (min == max) return;

    using difference_type = typename std::iterator_traits<ForwardIterator>::difference_type;
    std::vector<difference_type> counts(max - min + 1, 0);

    for (auto it = first ; it != last ; ++it) {
        ++counts[*it - min];
    }

    for (auto count: counts) {
        first = std::fill_n(first, count, min++);
    }
}

हालांकि यह केवल तब उपयोगी होता है जब सॉर्ट करने के लिए पूर्णांक की श्रेणी छोटी होती है (आम तौर पर संग्रह के आकार से बड़ी नहीं होती), गिनती प्रकार को अधिक सामान्य बनाने से इसे अपने सर्वोत्तम मामलों के लिए धीमा कर दिया जाता है। यदि रेंज को छोटा नहीं माना जाता है, तो इसके बजाय एक अन्य एल्गोरिदम जैसे रेडिक्स सॉर्ट , ska_sort या spreadsort का उपयोग किया जा सकता है।

विवरण छोड़ा गया :

  • हम संग्रह के माध्यम से पहले std::minmax_element पास से पूरी तरह से छुटकारा पाने के लिए पैरामीटर के रूप में एल्गोरिदम द्वारा स्वीकार किए गए मानों की सीमा की सीमा पारित कर सकते थे। इससे एल्गोरिदम भी तेज हो जाएगा जब उपयोगी रूप से छोटी सीमा सीमा अन्य माध्यमों से जानी जाती है। (यह सटीक नहीं होना चाहिए; निरंतर 0 से 100 गुजरना एक लाख से अधिक तत्वों के अतिरिक्त पास से कहीं अधिक बेहतर है, यह पता लगाने के लिए कि वास्तविक सीमा 1 से 95 है। यहां तक ​​कि 0 से 1000 भी इसके लायक होंगे; अतिरिक्त तत्व शून्य के साथ एक बार लिखा जाता है और एक बार पढ़ा जाता है)।

  • फ्लाई पर बढ़ती counts एक अलग पहला पास से बचने का एक और तरीका है। जब भी इसे बढ़ाना होता है तो counts आकार को दोगुना करना प्रति क्रमबद्ध तत्व (1) समय प्रतिस्थापित तत्व देता है (सबूत के लिए हैश टेबल सम्मिलन लागत विश्लेषण देखें कि घातीय उगाई कुंजी है)। एक नए max के अंत में बढ़ रहा है std::vector::resize साथ नया शून्य शून्य तत्वों को जोड़ने के लिए std::vector::resize आसान है। फ्लाई पर min बदलना और सामने वाले नए शून्य तत्वों को डालने से वेक्टर बढ़ने के बाद std::copy_backward साथ किया जा सकता है। फिर std::fill नए तत्वों को शून्य पर std::fill

  • counts बढ़ती लूप एक हिस्टोग्राम है। यदि डेटा अत्यधिक दोहराया जा सकता है, और डिब्बे की संख्या छोटी है, तो उसी बिन में स्टोर / रीलोड की सीरियलाइजिंग डेटा निर्भरता बाधा को कम करने के लिए एकाधिक सरणी पर अनलॉक करने योग्य हो सकता है। इसका मतलब है कि शुरुआत में शून्य पर अधिक मायने रखता है, और अंत में लूप के लिए और अधिक, लेकिन 0 से 100 संख्याओं के हमारे उदाहरण के लिए अधिकांश CPUs पर इसके लायक होना चाहिए, खासकर अगर इनपुट पहले से ही आंशिक रूप से (आंशिक रूप से) हो सकता है और एक ही संख्या के लंबे रन हैं।

  • उपरोक्त एल्गोरिदम में, हम एक min == max चेक का उपयोग जल्दी लौटने के लिए करते हैं जब प्रत्येक तत्व के समान मूल्य होता है (जिस स्थिति में संग्रह सॉर्ट किया जाता है)। इसके बजाय वास्तव में यह जांचना संभव है कि संग्रह को पहले से क्रमबद्ध किया गया है या नहीं, संग्रह के चरम मूल्यों को बिना किसी अतिरिक्त समय के बर्बाद कर दिया गया है (यदि पहला पास अभी भी न्यूनतम और अधिकतम अद्यतन करने के अतिरिक्त कार्य के साथ स्मृति को बाधित करता है)। हालांकि इस तरह के एक एल्गोरिदम मानक पुस्तकालय में मौजूद नहीं है और लिखना बाकी गिनती के प्रकार को लिखने से ज्यादा कठिन होगा। इसे पाठक के लिए एक अभ्यास के रूप में छोड़ दिया गया है।

  • चूंकि एल्गोरिदम केवल पूर्णांक मानों के साथ काम करता है, इसलिए उपयोगकर्ताओं को स्पष्ट प्रकार की गलतियों को रोकने से रोकने के लिए स्थिर दावे का उपयोग किया जा सकता है। कुछ संदर्भों में, std::enable_if_t साथ प्रतिस्थापन विफलता को प्राथमिकता दी जा सकती है।

  • जबकि आधुनिक सी ++ ठंडा है, भविष्य में सी ++ भी कूलर हो सकता है: संरचित बाइंडिंग और रेंज टीएस के कुछ हिस्सों में एल्गोरिदम भी क्लीनर बन जाएगा।







c++-faq