बुलबुले का जावास्क्रिप्ट कार्यान्वयन अन्य एल्गोरिदम को सॉर्ट करने की तुलना में बहुत तेज क्यों है?

Question

मैंने जावास्क्रिप्ट सॉर्टिंग एल्गोरिदम प्रदर्शन तुलना के बारे में कुछ research किया है, और अप्रत्याशित परिणाम मिले हैं। बबल सॉर्ट ने शैल सॉर्ट, क्विक सॉर्ट और मूल जावास्क्रिप्ट कार्यक्षमता जैसे अन्य लोगों की तुलना में बेहतर प्रदर्शन प्रदान किया। ऐसा क्यों होता है? शायद मैं अपने प्रदर्शन परीक्षण विधि में गलत हूँ?

आप मेरे शोध परिणाम here पा सकते हैं।

यहाँ कुछ एल्गोरिथ्म कार्यान्वयन उदाहरण हैं:

/** 
    * Bubble sort(optimized) 
    */ 
    Array.prototype.bubbleSort = function() 
    { 
    var n = this.length; 
    do { 
     var swapped = false; 
     for (var i = 1; i < n; i++) { 
      if (this[i - 1] > this[i]) { 
       var tmp = this[i-1]; 
       this[i-1] = this[i]; 
       this[i] = tmp; 
       swapped = true; 
      } 
     } 
    } while (swapped); 
    } 

    /** 
    * Quick sort 
    */ 
    Array.prototype.quickSort = function() 
    { 
     if (this.length <= 1) 
      return this; 

     var pivot = this[Math.round(this.length/2)]; 

     return this.filter(function (x) { return x < pivot }).quickSort().concat(
      this.filter(function (x) { return x == pivot })).concat(
      this.filter(function (x) { return x > pivot }).quickSort()); 
    } 

Answer 1

है ऐसा इसलिए है क्योंकि बुलबुला तरह तेजी से जब आप एक सरणी है कि पहले से ही हल कर छँटाई कर रहे हैं।

जैसा कि आप एक ही सरणी को बार-बार क्रमबद्ध कर रहे हैं, इसे पहले टेस्ट में पहले पुनरावृत्ति में क्रमबद्ध किया जाएगा, उसके बाद आप पहले से सॉर्ट किए गए सरणी को सॉर्ट कर रहे हैं।

एक सरणी को सॉर्ट करने के वास्तविक प्रदर्शन का परीक्षण करने के लिए जो पहले से सॉर्ट नहीं किया गया है, आपको प्रत्येक प्रकार के पुनरावृत्ति के लिए एक नया सरणी बनाना होगा।