एक निर्धारण क्विक्सॉर्ट क्या है?

Question

मैं क्विक्सोर्ट के बारे में पढ़ रहा हूं और पाया कि कभी-कभी इसे "निर्धारक क्विक्सोर्ट" के रूप में जाना जाता है।

क्या यह सामान्य क्विक्सॉर्ट का एक वैकल्पिक संस्करण है? एक सामान्य क्विक्सॉर्ट और एक निर्धारक क्विक्सोर्ट के बीच क्या अंतर है?

Answer 1

साधारण ("निर्धारक") क्विक्सोर्ट विशेष डेटासेट पर बहुत खराब व्यवहार कर सकता है (उदाहरण के तौर पर, पहले अपरिवर्तित तत्व को चुनने वाला एक कार्यान्वयन पहले से क्रमबद्ध डेटा पर ओ (एन^2) समय जटिलता है)।

यादृच्छिक क्विक्सोर्ट (जो निर्धारित रूप से चुनने के बजाय यादृच्छिक पिवट का चयन करता है) कभी-कभी सभी डेटासेट पर बेहतर अपेक्षित प्रदर्शन देने के लिए उपयोग किया जाता है।

Answer 2

क्विक्सोर्ट O(n log n) में अपेक्षित/औसत समय में चलता है, लेकिन O(n^2) सबसे खराब मामला। ऐसा तब होता है जब चुना गया पिवट लगातार न्यूनतम या अधिकतम होता है।

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

उत्तरार्द्ध विधि पिवोट चयन प्रक्रिया के निहित यादृच्छिकता के कारण quicksort nondeterministic प्रस्तुत करता है।

Answer 3

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

Answer 4

इसे विभाजन (या प्रसिद्ध विभाजन और विजेता से विभाजित कदम जो त्वरित क्रम में उपयोग किया जाता है) के साथ करना है। यदि हर बार आखिरी (या किसी भी स्थिति में पहला तत्व या तत्व, डेटा सेट को विभाजित होने पर हर बार एक ही स्थिति होनी चाहिए) विभाजन के लिए पिवट के रूप में प्रयोग किया जाता है तो यह निर्धारक त्वरित प्रकार है। यदि पिवट को यादृच्छिक रूप से चुना जाता है तो यह यादृच्छिक त्वरित प्रकार है।

यहां एक lecture note है जो इसे भर देता है।

मुझे आशा है कि यह

चियर्स

Answer 5

सामान्य में मदद करता है, एक तरह से एल्गोरिथ्म "नियतात्मक" है अगर यह लगातार हर बार ठीक उसी क्रम में तत्वों क्रमबद्ध करता है। आईडी पर सॉर्ट करने के लिए (एएससी) के रिकॉर्ड का एक सेट को देखते हुए:

1 Censu 
    11 Marju 
    4 Cikku 
    11 Lonzu 

तो एक छँटाई एल्गोरिथ्म लौट सकते हैं दोनों Censu, Cikk, Marju, Lonzu, या Censu, Cikku, Lonzu, Marju, के रूप में सही sortings। एक निर्धारिक क्रम वह है जो हमेशा एक ही आदेश देता है। यह हमेशा मामला नहीं होना चाहिए। क्विकॉर्ट के मामले में, अगर पिट्स को यादृच्छिक रूप से चुना जाता है तो एक तेज औसत प्रदर्शन प्राप्त कर सकता है (आदर्श रूप में आप औसत चुनते हैं, लेकिन यह महंगा हो सकता है)। हालांकि, यह एक लागत पर आता है: आपकी खोज अब निर्धारिती नहीं है।

Answer 6

क्या कई अन्य लोगों को पहले से ही के बारे में आपको बता चुका हूँ इसके अलावा

कैसे एक नियतात्मक त्वरित तरह कार्यान्वित किया जाता है और एक गैर नियतात्मक एक है, मैं एक, इस तरह के एक तरह से बहुत अधिक महत्वपूर्ण पहलू विश्वास है, यह है कि, साथ नियतात्मक quicksort, आप गैर-निर्धारिती क्विकॉर्ट्स के साथ, जब रिकॉर्ड सॉर्ट करते हैं, तो रिकॉर्ड के क्रम में हमेशा रिकॉर्ड का एक ही क्रम होता है, जब भी आप इस तरह के रिकॉर्ड चलाते हैं तो इस तरह के रिकॉर्ड अलग-अलग हो सकते हैं।

मुझे लगता है कि जब आपके पास गैर-अनन्य कुंजी हों तो आपको गैर-निर्धारिती Quicksorting का उपयोग नहीं करना चाहिए।

Answer 7

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

नियतात्मक

यह कैसे pivots के लिए चुना जाता है करने के लिए नीचे आता है । एक निर्धारक quicksort में, pivots या तो हमेशा एक ही सापेक्ष सूचकांक जैसे पहले, आखिरी, या मध्यम तत्व या पूर्व निर्धारित तत्व विकल्पों के औसत का उपयोग करके पिवोट चुनकर चुने जाते हैं। उदाहरण के लिए, पिवट के रूप में पहले, आखिरी और मध्य तत्वों के मध्य का चयन करना एक आम तरीका है। यहां तक ​​कि मध्य-3-विधि विधि के साथ मैंने अभी वर्णित किया है, कुछ डेटासेट आसानी से ओ (एन^2) समय जटिलता दे सकते हैं। एक उदाहरण डाटासेट तथाकथित अंग डेटा का सेट पाइप है:

array = [1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4,3,2,1] 

यादृच्छिक

Randomizated quicksorts सिर्फ एक यादृच्छिक धुरी चुन सकते हैं या अनियमित रूप से चुने इन्हीं में से कुछ संख्या की औसत उपयोग कर सकते हैं। ओ (एन^2) समय जटिलता की संभावना अभी भी है, लेकिन संभावना बहुत अधिक है, बहुत छोटा है और बढ़ते डेटासेट आकार के साथ छोटा हो जाता है।