हीप पर क्विक्सॉर्ट श्रेष्ठता क्रमबद्ध करें

Question

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

http://www.cs.auckland.ac.nz/software/AlgAnim/qsort3.html

http://users.aims.ac.za/~mackay/sorting/sorting.html

अनिवार्य रूप से, भले ही त्वरित प्रकार के लिए सबसे खराब स्थिति हे है (एन^2) यह:

Answer 1

प्रमुख कारकों में से एक यह है कि क्विक्सॉर्ट संदर्भ की स्थानीयता है - अगली चीज़ को एक्सेस करने के लिए आमतौर पर उस चीज़ को याद किया जाता है जिसे आपने अभी देखा था। इसके विपरीत, हेपसोर्ट काफी अधिक आसपास कूदता है। चूंकि जो चीजें एक साथ हैं, उन्हें एक साथ कैश किया जाएगा, क्विकॉर्ट तेजी से होता है।

हालांकि, क्विकसॉर्ट का सबसे खराब-मामला प्रदर्शन हेपॉर्ट्स की तुलना में काफी खराब है। चूंकि कुछ महत्वपूर्ण अनुप्रयोगों को गति प्रदर्शन की गारंटी की आवश्यकता होगी, ऐसे मामलों के लिए हेपसोर्ट सही तरीका है।

Answer 2

यहां पर कुछ स्पष्टीकरण है। :-)

Answer 3

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

Answer 4

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

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

Answer 5

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

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

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

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

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

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

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

मेरे कंप्यूटर पर सी # में नीचे कार्यान्वयन, रिलीज मोड पर चल रहा है, मध्य पिवट के साथ 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); 
}