quicksort धुरी

Question

क्रमबद्ध निम्नलिखित सरणी एक का उपयोग कर quicksort,

[6, 11, 4, 9, 8, 2, 5, 8, 13, 7] 

धुरी पहली और आखिरी तत्व, जैसे कि, (a[0] + a[size - 1])/2 (rounded down) का समांतर माध्य के रूप में चुना जाना चाहिए।

विभाजन और रिकर्सिव कॉल को एल्गोरिदम में सभी महत्वपूर्ण चरणों को दिखाएं।

---

मैं समझता हूं कि Quicksort का उपयोग करके सरणी को कैसे सॉर्ट करना है, हालांकि मुझे यकीन नहीं है कि पिवट की गणना कैसे करें। (पूर्णांक है 6)

धुरी तो 6 + 7 = 1313/2 = 6.5 करके की जाती है तो धुरी 2 (अर्थात 6 तत्व) है?

मुझे बाएं हाथ की ओर पिवट दिखाई देने वाले तत्वों को पता है, और पिवट से अधिक तत्व दाईं ओर दिखाई देते हैं, और विभाजन उप-सरणी को सॉर्ट करने के इस चरण को दोहराता है।

किसी भी मदद की सराहना की जाएगी।

Answer 1

क्विकॉर्ट के लिए, पिवट आप जो भी तत्व चाहते हैं वह हो सकता है। Wikipedia देखें।

समस्या को आसानी से धुरी के लिए या तो एक यादृच्छिक सूचकांक चुनने बीच सूचकांक विभाजन के या (विशेष रूप से लंबे समय तक विभाजन के लिए) की मंझला चुनने का चयन करके हल किया गया था पहले, मध्य और अंतिम धुरी के विभाजन के लिए तत्व

तीन विकल्प इस प्रकार:

• फाई आरएसटी तत्व
• मध्य तत्व
• पहले, मध्य और आखिरी के मध्य।

और तुम मामले प्रथम और अंतिम तत्व का मतलब का उपयोग करने में मूल्य आप देना होगा:

6 + 7 = 13 
13/2 = 6.5 
6.5 rounded down = 6 

Answer 2

जिस तरह से सवाल कहा जाता है, पिवट केवल 6 होना चाहिए और सरणी में 6 वां आइटम नहीं होना चाहिए।

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

नोट: अपने सरणी में तत्वों को इंडेक्स करने के तरीके से सावधान रहें। आपने कहा कि 6 वां तत्व '2' है, जब यह '5' हो सकता है यदि आपकी प्रोग्रामिंग भाषा 0 से

Answer 3

आपका पिवट 6 है। आपका पिवोट 6 वें तत्व नहीं है अब आप निम्न एल्गोरिथ लागू कर सकते हैं ।

function quicksort(array) 
var list less, greater 
if length(array) ≤ 1 
    return array // an array of zero or one elements is already sorted 
select and remove a pivot value pivot from array 
for each x in array 
    if x ≤ pivot then append x to less 
    else append x to greater 
return concatenate(quicksort(less), pivot, quicksort(greater)) 

Answer 4

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