algorithm Quicksort बनाम हेपसोर्ट




sorting heapsort (9)

खैर यदि आप आर्किटेक्चर स्तर पर जाते हैं ... हम कैश मेमोरी में कतार डेटा संरचना का उपयोग करते हैं। इसलिए कतार में जो भी उपलब्ध है, उसे क्रमबद्ध किया जाएगा। त्वरित क्रम में हमारे पास सरणी को किसी भी लंबाई में विभाजित करने में कोई समस्या नहीं है ... लेकिन ढेर में सॉर्ट करें (सरणी का उपयोग करके) ऐसा हो सकता है कि पैरेंट कैश में उपलब्ध उप सरणी में मौजूद न हो और फिर इसे कैश मेमोरी में लाया जाए ... जो समय लेने वाला है। यह क्विकॉर्ट सबसे अच्छा है !! 😀

क्विकॉर्ट और हेपसोर्ट दोनों जगह-जगह सॉर्टिंग करते हैं। कौनसा अच्छा है? उन अनुप्रयोगों और मामलों में क्या हैं जिन्हें प्राथमिकता दी जाती है?


मेरे लिए हेपॉर्ट और क्विकॉर्ट के बीच एक बहुत ही मौलिक अंतर है: उत्तरार्द्ध एक रिकर्सन का उपयोग करता है। रिकर्सिव एल्गोरिदम में ढेर रिकर्सन की संख्या के साथ बढ़ता है। इससे कोई फर्क नहीं पड़ता कि एन छोटा है, लेकिन अभी मैं दो मैट्रिस को एन = 10 ^ 9 !! के साथ क्रमबद्ध कर रहा हूं। कार्यक्रम में लगभग 10 जीबी रैम लगता है और कोई अतिरिक्त मेमोरी मेरे कंप्यूटर को वर्चुअल डिस्क मेमोरी में स्वैप करना शुरू कर देगी। मेरी डिस्क एक रैम डिस्क है, लेकिन अभी भी इसके लिए स्वैपिंग गति में एक बड़ा अंतर बनाता है। तो सी ++ में कोडित एक स्टैपैक में जिसमें एडजस्टेबल आयाम मैट्रिस शामिल हैं, प्रोग्रामर के लिए पहले से अज्ञात आकार के साथ, और गैरपरैमेट्रिक सांख्यिकीय प्रकार की सॉर्टिंग मैं बहुत बड़ी डेटा मैट्रिक्स के साथ उपयोग करने में देरी से बचने के लिए हेपसोर्ट पसंद करता हूं।


अनि। quick sort क्रम और merge sort बीच दोनों प्रकार के स्थान क्रमबद्ध होते हैं, क्वॉस्ट केस के बीच एक अंतर होता है जो क्विक केस के चलने वाले समय के त्वरित समय के लिए चलने का समय होता है O(n^2) और हेप सॉर्ट के लिए यह अभी भी O(n*log(n)) और डेटा की औसत मात्रा के लिए त्वरित प्रकार अधिक उपयोगी होगा। चूंकि यह यादृच्छिक एल्गोरिदम है इसलिए सही उत्तर प्राप्त करने की संभावना है। कम समय में आपके द्वारा चुने गए पिवट तत्व की स्थिति पर निर्भर करेगा।

तो ए

अच्छी कॉल: एल और जी के आकार प्रत्येक 3s / 4 से कम हैं

खराब कॉल: एल और जी में से एक का आकार 3s / 4 से बड़ा है

छोटी राशि के लिए हम सम्मिलन के प्रकार के लिए जा सकते हैं और बहुत बड़ी मात्रा में डेटा ढेर प्रकार के लिए जा सकते हैं।


बहुत बड़े इनपुट से निपटने पर हीप सॉर्ट एक सुरक्षित शर्त है। एसिम्प्टोटिक विश्लेषण से पता चलता है कि सबसे खराब मामले में हेपसॉर्ट के विकास का क्रम Big-O(n logn) , जो क्विक्सोर्ट के Big-O(n^2) से सबसे खराब मामले के रूप में बेहतर है। हालांकि, Heapsort एक अच्छी तरह से कार्यान्वित त्वरित प्रकार की तुलना में अधिकांश मशीनों पर अभ्यास में कुछ हद तक धीमा है। हेपसोर्ट एक स्थिर सॉर्टिंग एल्गोरिदम भी नहीं है।

Quicksort की तुलना में हेपॉर्ट अभ्यास में धीमा है कारण त्वरित संदर्भ में संदर्भ (" https://en.wikipedia.org/wiki/Locality_of_reference ") के बेहतर इलाके के कारण है, जहां डेटा तत्व अपेक्षाकृत निकट भंडारण स्थानों के भीतर हैं। सिस्टम जो संदर्भ के मजबूत इलाके का प्रदर्शन करते हैं वे प्रदर्शन अनुकूलन के लिए महान उम्मीदवार हैं। ढेर प्रकार, हालांकि, बड़े छलांग के साथ सौदा करता है। यह छोटे इनपुट के लिए quicksort अधिक अनुकूल बनाता है।


ज्यादातर परिस्थितियों में, जल्दी बनाम थोड़ा तेज होना अप्रासंगिक है ... आप कभी कभी कभी भी धीमी गति से धीमी गति से नहीं आना चाहते हैं। यद्यपि आप धीमी परिस्थितियों से बचने के लिए क्विकॉर्ट को ट्विक कर सकते हैं, फिर भी आप मूल क्विकॉर्ट का लालित्य खो देते हैं। तो, ज्यादातर चीजों के लिए, मैं वास्तव में हीपॉर्ट पसंद करता हूं ... आप इसे अपने पूर्ण सरल लालित्य में कार्यान्वित कर सकते हैं, और कभी भी धीमी गति से नहीं मिल सकते हैं।

उन स्थितियों के लिए जहां आप ज्यादातर मामलों में अधिकतम गति चाहते हैं, हेपॉर्ट पर क्विकॉर्ट को प्राथमिकता दी जा सकती है, लेकिन न ही सही जवाब हो सकता है। गति-महत्वपूर्ण स्थितियों के लिए, स्थिति की जानकारी बारीकी से जांचना उचित है। उदाहरण के लिए, मेरे कुछ गति-महत्वपूर्ण कोड में, यह बहुत आम है कि डेटा पहले ही सॉर्ट या पास-सॉर्ट किया गया है (यह कई संबंधित फ़ील्ड को अनुक्रमणित कर रहा है जो अक्सर या तो ऊपर या नीचे जाते हैं या एक दूसरे के विपरीत ऊपर और नीचे जाते हैं, तो एक बार जब आप एक से सॉर्ट करते हैं, तो दूसरों को या तो सॉर्ट या रिवर्स-सॉर्ट या बंद कर दिया जाता है ... इनमें से कोई भी क्विकस्टोर्ट को मार सकता है)। उस मामले के लिए, मैंने न तो लागू किया ... इसके बजाय, मैंने डिजस्ट्रा के स्मूथोर्ट को लागू किया ... एक हीपॉर्ट संस्करण जो ओ (एन) है जब पहले से ही सॉर्ट या पास-सॉर्ट किया गया है ... यह इतना सुरुचिपूर्ण नहीं है, समझने में बहुत आसान नहीं है, लेकिन तेज़ ... पढ़ें http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF यदि आप कोड के लिए कुछ और चुनौतीपूर्ण चाहते हैं।


हेप्सोर्ट के पास ओ (एन * लॉग (एन)) का सबसे खराब चलने वाला मामला होने का लाभ है, इसलिए ऐसे मामलों में जहां क्विकॉर्टोर्ट खराब प्रदर्शन कर रहा है (आमतौर पर सॉर्ट किए गए डेटा सेट आमतौर पर) हेपसोर्ट को बहुत पसंद किया जाता है।


http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort3.html में कुछ विश्लेषण है।

इसके अलावा, विकिपीडिया से:

क्विकॉर्ट का सबसे प्रत्यक्ष प्रतियोगी हेपॉर्ट है। हेपसॉर्ट आमतौर पर क्विकॉर्ट से थोड़ा धीमा होता है, लेकिन सबसे खराब केस चलने का समय हमेशा Θ (nlogn) होता है। Quicksort आमतौर पर तेज़ है, हालांकि introsort संस्करण को छोड़कर सबसे खराब केस प्रदर्शन का मौका रहता है, जो खराब मामले का पता चला है जब हेपॉर्ट में स्विच करता है। यदि यह पहले से ज्ञात है कि हेपसॉर्ट आवश्यक होने जा रहा है, तो इसका उपयोग सीधे घुसपैठ करने के लिए घुसपैठ के इंतजार से तेज होगा।


Quicksort-Heapsort इन-प्लेस हाइब्रिड वास्तव में भी दिलचस्प हैं, क्योंकि उनमें से अधिकतर को केवल सबसे खराब मामले में एन * लॉग एन तुलना की आवश्यकता होती है (वे एसिम्प्टोटिक्स की पहली अवधि के संबंध में इष्टतम हैं, इसलिए वे सबसे खराब परिस्थितियों से बचते हैं Quicksort के), ओ (लॉग एन) अतिरिक्त जगह और वे डेटा के पहले से आदेशित सेट के संबंध में Quicksort के अच्छे व्यवहार के कम से कम "आधे" को संरक्षित करते हैं। Http://ikxiv.org/pdf/1209.4214v1.pdf में डिकर्ट और वीस द्वारा एक अत्यंत रोचक एल्गोरिदम प्रस्तुत किया गया है:

  • Sqrt (n) तत्वों के एक यादृच्छिक नमूने के औसत के रूप में एक पिवट पी का चयन करें (यह अधिक 24 वर्ग (एन) तुलना में तर्जन और सह के एल्गोरिदम के माध्यम से किया जा सकता है, या 5 वर्ग (एन) तुलना अधिक जटिल मकड़ी के माध्यम से तुलना में किया जा सकता है Schonhage के फैक्टरी एल्गोरिदम);
  • Quicksort के पहले चरण में अपने सरणी को दो हिस्सों में विभाजित करें;
  • सबसे छोटे हिस्से को तेज़ करें और एक ढेर को एन्कोड करने के लिए ओ (लॉग एन) अतिरिक्त बिट्स का उपयोग करें जिसमें प्रत्येक बाएं बच्चे के भाई से अधिक मूल्य होता है;
  • संक्षेप में ढेर की जड़ निकालें, जब तक यह ढेर के पत्ते तक नहीं पहुंच जाता तब तक रूट द्वारा छोड़े गए लैक्यून को नीचे छोड़ दें, फिर सरणी के दूसरे भाग से लिया गया उचित तत्व के साथ लैक्यून भरें;
  • सरणी के शेष गैर-आदेशित भाग पर पुनरावृत्ति करें (यदि पी को सटीक औसत के रूप में चुना जाता है, तो बिल्कुल कोई रिकर्सन नहीं होता है)।

हेपसोर्ट ओ (एन लॉग एन) गारंटी है, Quicksort में सबसे खराब मामले की तुलना में क्या बेहतर है। हेर्सेर्ट को किसी अन्य सरणी के लिए मेरजेसोर्ट द्वारा आवश्यक आदेश देने के लिए अधिक मेमोरी की आवश्यकता नहीं है। तो कॉमर्सियल एप्लिकेशन क्विक्सोर्ट के साथ क्यों चिपकते हैं? क्विक्सोर्ट क्या है जो दूसरों के कार्यान्वयन पर इतना खास है?

मैंने स्वयं एल्गोरिदम का परीक्षण किया है और मैंने देखा है कि क्विक्सोर्ट में वास्तव में कुछ खास है। यह तेज़, तेजी से तेज़ चलता है और एल्गोरिदम मर्ज करता है।

Quicksort का रहस्य है: यह लगभग अनावश्यक तत्व स्वैप नहीं करता है। स्वैप समय लेने वाला है।

हेपसोर्ट के साथ, भले ही आपका सभी डेटा पहले से ही आदेश दिया गया हो, फिर भी आप सरणी को ऑर्डर करने के लिए 100% तत्वों को स्वैप करने जा रहे हैं।

विलय के साथ, यह भी बदतर है। आप किसी अन्य सरणी में 100% तत्व लिखने जा रहे हैं और इसे मूल में वापस लिख सकते हैं, भले ही डेटा पहले से ही आदेश दिया गया हो।

Quicksort के साथ आप पहले से आदेश दिया गया है कि स्वैप नहीं है। यदि आपका डेटा पूरी तरह से आदेश दिया गया है, तो आप लगभग कुछ भी स्वैप नहीं करते हैं! यद्यपि सबसे खराब मामले के बारे में बहुत परेशानी है, लेकिन पिवोट की पसंद पर थोड़ा सुधार, सरणी के पहले या अंतिम तत्व को प्राप्त करने के अलावा कोई भी इससे बच सकता है। यदि आपको पहले, अंतिम और मध्य तत्व के बीच मध्यवर्ती तत्व से पिवट मिलता है, तो यह सबसे खराब स्थिति से बचने के लिए उपयुक्त है।

Quicksort में बेहतर क्या सबसे बुरा मामला नहीं है, लेकिन सबसे अच्छा मामला है! सबसे अच्छे मामले में आप तुलना की समान संख्या करते हैं, ठीक है, लेकिन आप लगभग कुछ भी स्वैप नहीं करते हैं। औसतन मामले में आप तत्वों का हिस्सा स्वैप करते हैं, लेकिन सभी तत्व नहीं, जैसे हेपसोर्ट और मेर्गेसॉर्ट में। यही वह है जो क्विक्सोर्ट को सबसे अच्छा समय देता है। कम स्वैप, अधिक गति।

मेरे कंप्यूटर पर सी # में नीचे कार्यान्वयन, रिलीज मोड पर चल रहा है, मध्य पिवट के साथ 3 सेकंड तक और 30 सेकंड तक बेहतर पिवट के साथ धड़कता है। (हाँ, एक अच्छा पिवट पाने के लिए एक ओवरहेड है)।

static void Main(string[] args)
{
    int[] arrToSort = new int[100000000];
    var r = new Random();
    for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);

    Console.WriteLine("Press q to quick sort, s to Array.Sort");
    while (true)
    {
        var k = Console.ReadKey(true);
        if (k.KeyChar == 'q')
        {
            // quick sort
            Console.WriteLine("Beg quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            QuickSort(arrToSort, 0, arrToSort.Length - 1);
            Console.WriteLine("End quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
        }
        else if (k.KeyChar == 's')
        {
            Console.WriteLine("Beg Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            Array.Sort(arrToSort);
            Console.WriteLine("End Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
        }
    }
}

static public void QuickSort(int[] arr, int left, int right)
{
    int begin = left
        , end = right
        , pivot
        // get middle element pivot
        //= arr[(left + right) / 2]
        ;

    //improved pivot
    int middle = (left + right) / 2;
    int
        LM = arr[left].CompareTo(arr[middle])
        , MR = arr[middle].CompareTo(arr[right])
        , LR = arr[left].CompareTo(arr[right])
        ;
    if (-1 * LM == LR)
        pivot = arr[left];
    else
        if (MR == -1 * LR)
            pivot = arr[right];
        else
            pivot = arr[middle];
    do
    {
        while (arr[left] < pivot) left++;
        while (arr[right] > pivot) right--;

        if(left <= right)
        {
            int temp = arr[right];
            arr[right] = arr[left];
            arr[left] = temp;

            left++;
            right--;
        }
    } while (left <= right);

    if (left < end) QuickSort(arr, left, end);
    if (begin < right) QuickSort(arr, begin, right);
}




heapsort