अभ्यास में क्विकॉर्ट का उपयोग क्यों किया जाता है?

Question

quicksort बुरी से बुरी हालत (एन) हे के प्रदर्शन है, लेकिन अभी भी वैसे भी व्यवहार में व्यापक रूप से इस्तेमाल किया जाता है। ऐसा क्यों है?

Answer 1

औसत पर यह सबसे तेज़ तुलना क्रम है (बीत चुके समय के मामले में)।

Answer 2

क्योंकि, सामान्य मामले में, यह सबसे तेज़ सॉर्टिंग एल्गोरिदम में से एक है।

Answer 3

quicksort की औसत asymptotic क्रम O(nlogn) है और यह छोटे स्थिरांक (तंग छोरों) की वजह से heapsort से आम तौर पर और अधिक कुशल है। वास्तव में, एक सैद्धांतिक रैखिक समय औसत चयन एल्गोरिदम है जिसे आप हमेशा सर्वोत्तम पिवट खोजने के लिए उपयोग कर सकते हैं, जिसके परिणामस्वरूप सबसे खराब स्थिति O(nlogn) हो सकती है। हालांकि, सामान्य क्विकॉर्ट आमतौर पर इस सैद्धांतिक से तेज है।

इसे और अधिक समझदार बनाने के लिए, संभावना है कि quicksort O(n2) में खत्म हो जाएगा पर विचार करें। यह सिर्फ 1/n! है जिसका अर्थ है कि यह लगभग उस बुरे मामले का सामना नहीं करेगा।

Answer 4

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

quicksort:

• Θ (n लॉग n) की औसत समय जटिलता है; (लॉग n)
• Θ की अंतरिक्ष जटिलता के साथ लागू किया जा सकता है;

यह भी ध्यान में रखते हैं कि बड़े ओ नोटेशन किसी भी स्थिरांक को ध्यान में नहीं रखता है, लेकिन व्यावहारिक रूप से यह एल्गोरिदम कुछ गुना तेजी से भिन्न होता है। Θ (n लॉग n) का अर्थ है, कि एल्गोरिथ्म में कश्मीर   n   लॉग (n), जहां कश्मीर स्थिर है निष्पादित करता है। क्विक्सोर्ट तुलनात्मक क्रमबद्ध एल्गोरिदम है जो सबसे कम के के साथ है।

Answer 5

यह इंगित करने लायक हो सकता है कि सी में लाइब्रेरी फ़ंक्शन qsort() है, लेकिन कोई आवश्यकता नहीं है कि इसे वास्तविक क्विकॉर्ट का उपयोग करके लागू किया जाए, जो कि कंपाइलर विक्रेता पर निर्भर है।

Answer 6

हालांकि सबसे तेजी से होने के अलावा, इसके बारे में कुछ बुरा मामले परिदृश्यों यह छँटाई से पहले सरणी फेरबदल से बचा जा सकता है। चूंकि छोटे डेटा सेट के साथ इसकी कमजोरी के कारण, डेटासेट छोटे होने के कारण स्पष्ट रूप से बड़ी समस्या नहीं है और सॉर्ट टाइम शायद छोटे हैं।

उदाहरण के तौर पर, मैंने क्विकॉर्ट और बबल प्रकार के लिए एक पायथन फ़ंक्शन लिखा था। बबल प्रकार में 10,000 रिकॉर्ड, 7500 के लिए 11 सेकंड और 5000 के लिए 5 सेकंड करने के लिए ~ 20 सेकंड लगते हैं। क्विकॉर्ट लगभग 0.15 सेकेंड में इन सभी प्रकारों को करता है! quicksort बनाम mergesort के लिए एन एलजी n के लिए 1.44 n एलजी n (उम्मीद) -

Answer 7

दिलचस्प बात यह है quicksort अधिक mergesort की तुलना में औसतन तुलना करता है।यदि सभी परिपक्व तुलना की तुलना में थे, तो विलय त्वरित रूप से क्विकॉर्ट के लिए बेहतर होगा।

कारण यह है कि quicksort तेज है यह कई अन्य वांछनीय गुणों है कि आधुनिक हार्डवेयर पर बहुत अच्छी तरह से काम करते हैं होता है। उदाहरण के लिए, क्विकॉर्ट को गतिशील आवंटन की आवश्यकता नहीं होती है। रिकर्सन के लिए आवश्यक स्टैक फ्रेम को स्टोर करने के लिए यह केवल ओ (लॉग एन) स्टैक स्पेस (सबसे खराब केस अगर सही ढंग से कार्यान्वित किया जाता है) का उपयोग करके मूल सरणी पर जगह-जगह पर काम कर सकता है। यद्यपि विलय करने के लिए विलय किया जा सकता है, ऐसा करने पर आमतौर पर मर्ज चरण के दौरान एक विशाल प्रदर्शन दंड पर आता है। हेपसोर्ट जैसे अन्य सॉर्टिंग एल्गोरिदम भी इस संपत्ति में हैं।

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

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

क्विक्सॉर्ट के साथ एकमात्र मुद्दा यह संभावना है कि यह ओ (एन) में गिरावट आती है, जो बड़े डेटा सेट पर बहुत गंभीर हो सकती है। इससे बचने का एक तरीका यह है कि एल्गोरिदम स्वयं पर आत्मनिरीक्षण करें और उस मामले में धीमे लेकिन अधिक भरोसेमंद एल्गोरिदम पर स्विच करें जहां यह खराब हो। इस एल्गोरिथ्म, introsort कहा जाता है, एक महान संकर छँटाई एल्गोरिथ्म है कि रोग के मामले बिना quicksort के अनेक लाभ प्राप्त करता है।

सारांश में:

• quicksort ढेर प्रत्यावर्तन में इस्तेमाल किया फ्रेम, जो हे (लॉग एन) जगह लेने के लिए छोड़कर यथा-स्थान है।
• quicksort संदर्भ के अच्छे इलाके है।
• quicksort आसानी से parallelized है।

यह खाता है कि क्यों पेपर पर सॉर्टिंग एल्गोरिदम को बेहतर प्रदर्शन करना पड़ता है।

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

Answer 8

Bcs यह अच्छी तरह से बड़े के साथ ओ (NlogN) जटिलता सेट डेटा पर काम के साथ एल्गोरिथ्म से एक है। यह जगह एल्गोरिदम भी है जो निरंतर स्थान लेता है। पिवोट तत्व को बुद्धिमानी से चुनकर हम त्वरित क्रम के खराब मामले से बच सकते हैं और हमेशा क्रमबद्ध सरणी पर ओ (एनएलओएनएन) में प्रदर्शन करेंगे।