जावास्क्रिप्ट Quicksort में अनंत रिकर्सन?

Question

यहां लिखा गया quicksort कोड है। समारोह काम नहीं करता है क्योंकि यह आधार मामले तक नहीं पहुंच सकता है। यदि मैं कंसोल पर पिवट, r और l लॉग करता हूं, तो वे वही रहते हैं चाहे सॉर्ट फ़ंक्शन को कितनी बार बुलाया जाता है। तो मुझे आश्चर्य है कि तर्क l, r वास्तव में फ़ंक्शन में डेटा के रूप में पारित नहीं किया गया है। यह क्यों हुआ?

function sort(data){ 
    if(data.length < 2){ 
     return data; 
    } 
    else{ 
     var l = []; 
     var r = []; 
     var pivot = parseInt(data.length/2); 
     for(i=0; i<data.length; i++){ 
      if(data[i] > data[pivot]){ 
       r.push(data[i]); 
      } 
      else{ 
       l.push(data[i]); 
      } 
     } 
     return sort(l).concat(sort(r)); 
    } 
} 

Answer 1

मुझे लगता है कि यहां मुद्दा यह है कि आपका विभाजन चरण आवश्यक रूप से इनपुट सरणी को कम नहीं करता है। उदाहरण के लिए, अगर आप [1, 2] सॉर्ट करने का प्रयास करते हैं तो पता लगाएं कि क्या होता है। इस मामले में, आपका पिवोट तत्व तत्व 2 होगा। चूंकि 1> 2 गलत है, 1 l सूची में जोड़ा गया है। चूंकि 2> 2 गलत है, 2 l सूची में जोड़ा गया है। नतीजतन, सूची l पर आपके रिकर्सिव कॉल में आपके मूल कॉल के समान ही तर्क होंगे, जो अनंत रिकर्सन का कारण बनता है।

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

function sort(data){ 
    if (data.length < 2){ 
    return data; 
    } else { 
    var l = []; 
    var r = []; 
    var e = []; 
    var i = 0; 
    var pivot = (data.length/2) | 0; 

    for(i = 0; i < data.length; i++) { 
     if (data[i] > data[pivot]) { 
     r.push(data[i]); 
     } else if (data[i] < data[pivot]) { 
     l.push(data[i]); 
     } else { 
     e.push(data[i]); 
     } 
    } 
    return sort(l).concat(e, sort(r)); 
    } 
} 

इस नए संस्करण में स्पष्ट रूप से समूहों बराबर तत्वों, इसलिए वे रिकर्सिवली पुनरावर्ती कॉल की या तो द्वारा पृथक नहीं कर रहे हैं। यह भी नकली तत्वों को सुदृढ़ रूप से संभालता है।

आशा है कि इससे मदद मिलती है!

Answer 2

जावास्क्रिप्ट संदर्भ द्वारा वस्तुओं को पास करता है (सरणी वस्तुएं भी हैं)। यदि आप उन्हें मूल्य से पास करना चाहते हैं, तो आपको here समझाए गए अनुसार स्प्लिस फ़ंक्शन का उपयोग करने की आवश्यकता है।

ध्यान दें कि इससे आपके डेटा की बहुत सारी प्रतियां बन जाएंगी। आप शायद मूल प्रकार() फ़ंक्शन का उपयोग करना चाहते हैं।

Answer 3

आप धुरी तत्व के रूप में सरणी का सबसे बड़ा मान लेने, तो data के सभी मान सरणी l और r में कोई भी में खत्म हो जाएगा। इस प्रकार रिकर्सन कभी नहीं रुक जाएगा (और l, r और pivot समान मानों पर रखें)। जब तक यह एक मस्तिष्क व्यायाम नहीं होता है, data.sort() का उपयोग करके बेहतर काम करना चाहिए। ;)