algorithm हेप सॉर्ट पर Quicksort श्रेष्ठता




sorting big-o (4)

हीप सॉर्ट में O(nlogn) की सबसे खराब केस जटिलता है जबकि क्विक्सोर्ट में O(n^2) । लेकिन साम्राज्यपूर्ण साक्ष्य कहते हैं कि क्विकॉर्ट बेहतर है। ऐसा क्यों है?


बड़े-ओ नोटेशन का अर्थ है कि एन आइटम को सॉर्ट करने के लिए आवश्यक समय फ़ंक्शन c*n*log(n) , जहां c कुछ अनिर्दिष्ट निरंतर कारक है। कोई कारण नहीं है कि निरंतर c heapsort और heapsort लिए समान क्यों होना चाहिए। तो असली सवाल यह है कि आप उन्हें अपेक्षाकृत तेज़ क्यों होने की उम्मीद करेंगे?

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


औसत-मामला जटिलता, और तथ्य यह है कि आप क्विक्सोर्ट में सबसे बुरी स्थिति जटिलता के जोखिम को कम करने के लिए सरल कदम उठा सकते हैं (उदाहरण के लिए एक चयनित स्थिति की बजाय तीन तत्वों के औसत के रूप में पिवट का चयन करें)।


हेपसोर्ट ओ (एन लॉग एन) गारंटी है, 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