स्थिर, कुशल प्रकार?

Question

मैं एक असामान्य साहचर्य सरणी कार्यान्वयन है कि बहुत अंतरिक्ष कुशल है बनाने के लिए कोशिश कर रहा हूँ, और मैं एक छँटाई कलन विधि है, उन सभी को पूरा करता है निम्नलिखित:

1. स्थिर (के साथ तत्वों के सापेक्ष आदेश को बदल नहीं करता है बराबर चाबियाँ।)
2. यथा-स्थान या लगभग यथा-स्थान (ओ (लॉग एन) ढेर ठीक है, लेकिन कोई हे (एन) स्थान उपयोग या ढेर आवंटन।
3. O (n लॉग ऑन एन) समय जटिलता।

यह भी ध्यान रखें कि सॉर्ट करने के लिए डेटा संरचना एक arra है y।

यह देखना आसान है कि इनमें से किसी भी 2 में से किसी एक से मेल खाता है (सम्मिलन क्रम 1 और 2 मैच, सॉर्ट मैचों 1 और 3 मर्ज करें, हेप सॉर्ट मैचों 2 और 3), लेकिन मैं जीवन के लिए नहीं कर सकता मुझे कुछ भी मिलता है जो इन तीनों मानदंडों से मेल खाता है।

Answer 1

क्विकॉर्ट के बारे में क्या?

एक्सचेंज भी ऐसा कर सकता है, आपकी शर्तों से अधिक "स्थिर" हो सकता है, लेकिन क्विकॉर्ट तेजी से है।

Answer 2

मर्ज सॉर्ट को मेरे स्थान पर होने के लिए लिखा जा सकता है। यह सबसे अच्छा मार्ग हो सकता है।

Answer 3

शायद shell sort? अगर मुझे अपने डेटा स्ट्रक्चर कोर्स को सही तरीके से याद किया जाता है, तो यह स्थिर हो जाता है, लेकिन यह खराब समय है ओ (एन लॉग^2 एन), हालांकि यह लगभग सॉर्ट किए गए डेटा पर ओ (एन) करता है। यह सम्मिलन प्रकार पर आधारित है, इसलिए यह जगह में है।

Answer 4

Wikipedia पर सॉर्ट एल्गोरिदम की एक सूची है। इसमें निष्पादन समय, स्थिरता और आवंटन द्वारा वर्गीकरण शामिल है।

आपकी सबसे अच्छी शर्त शायद स्थिर होने के लिए एक कुशल अस्थिर प्रकार को संशोधित करने जा रही है, जिससे इसे कम कुशल बना दिया जा सके।

Answer 5

नोट: मानक quicksort ओ (एन लॉग एन) नहीं है! सबसे बुरे मामले में, यह ओ (एन^2) समय तक ले सकता है। समस्या यह है कि आप एक तत्व पर पिवट कर सकते हैं जो औसत से बहुत दूर है, ताकि आपकी रिकर्सिव कॉल अत्यधिक असंतुलित हो।

इसका मुकाबला करने का एक तरीका है, जो मध्यस्थ के करीब होने के लिए सावधानीपूर्वक, या कम से कम संभवतः एक औसत व्यक्ति को चुनना है। यह आश्चर्य की बात है कि आप वास्तव में रैखिक समय में सटीक औसत प्राप्त कर सकते हैं, हालांकि आपके मामले में ऐसा लगता है कि आप गति की परवाह करते हैं, इसलिए मैं इसका सुझाव नहीं दूंगा।

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

वैसे, मर्ज सॉर्ट जगह में किया जा सकता है, हालांकि यह जगह और स्थिर दोनों करना मुश्किल है।

Answer 6

स्थिर जगह-जगह मर्ज एल्गोरिदम की एक श्रेणी है, हालांकि वे ओ (एन) में छिपी हुई उच्च स्थिरता के साथ जटिल और रैखिक हैं। अधिक जानने के लिए, this article, and its bibliography पर एक नज़र डालें।

संपादित करें: विलय चरण रैखिक है, इस प्रकार mergesort nlog_n है।

Answer 7

ओ (एन लॉग एन) के बारे में ज्यादा चिंता न करें जब तक आप यह प्रदर्शित नहीं कर सकते कि यह महत्वपूर्ण है। यदि आप एक ओ (एन^2) एल्गोरिदम को काफी कम स्थिरता के साथ पा सकते हैं, तो इसके लिए जाएं!

यदि आपका डेटा अत्यधिक बाधित है तो सामान्य सबसे खराब स्थिति परिदृश्य प्रासंगिक नहीं है।

संक्षेप में: कुछ परीक्षण चलाएं।

Answer 8

क्योंकि आपके तत्व सरणी में हैं (बजाय, एक लिंक्ड सूची के बजाय), आपके पास सरणी इंडेक्स में आपके मूल ऑर्डर के बारे में कुछ जानकारी है। जब तक तरह ही प्रदर्शन करती तत्व स्वैप

function cmp(ar, idx1, idx2) 
{ 
    // first compare elements as usual 
    rc = (ar[idx1]<ar[idx2]) ? -1 : ((ar[idx1]>ar[idx2]) ? 1 : 0); 

    // if the elements are identical, then compare their positions 
    if(rc != 0) 
     rc = (idx1<idx2) ? -1 : ((idx1>idx2) ? 1 : 0); 

    return rc; 
} 

इस तकनीक को किसी भी प्रकार स्थिर बनाने के लिए इस्तेमाल किया जा सकता,: आप अपने प्रकार और तुलना कार्यों लेखन सूचकांक के बारे में पता होना करने के लिए कर इस का लाभ ले सकते। तत्वों के सूचकांक बदल जाएंगे, लेकिन समान तत्वों का सापेक्ष क्रम वही रहेगा, इसलिए क्रम मजबूत बना हुआ है। यह हेपसोर्ट जैसे किसी प्रकार के लिए बॉक्स से बाहर काम नहीं करेगा क्योंकि मूल हेपिसिफिकेशन रिश्तेदार आदेश को "फेंक देता है", हालांकि आप इस विचार को अन्य प्रकारों में अनुकूलित करने में सक्षम हो सकते हैं।

Answer 9

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

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

मैंने इस विधि का उपयोग C के qsort() फ़ंक्शन के साथ स्वयं लिखने से बचने के लिए किया है। प्रत्येक रिकॉर्ड में 32-बिट पूर्णांक जोड़ा गया है और qsort() पर कॉल करने से पहले प्रारंभिक अनुक्रम संख्या के साथ पॉप्युलेट किया गया है।

फिर तुलना फ़ंक्शन ने और अनुक्रम की जांच की (यह गारंटी देता है कि कोई डुप्लिकेट कुंजी नहीं है), क्विकॉर्ट को एक स्थिर में बदलना। मुझे याद है कि यह अभी भी डेटा सेट के लिए अंतर्निहित स्थिर विलय को बेहतर प्रदर्शन करता है।

आपका माइलेज भिन्न हो सकता है, इसलिए हमेशा याद रखें: मापें, अनुमान लगाएं!

Answer 10

शायद मैं थोड़ी सी रट में हूं, लेकिन मुझे हाथ-कोडित मर्ज सॉर्ट पसंद है। यह सरल, स्थिर और अच्छी तरह से व्यवहार किया जाता है। अतिरिक्त अस्थायी भंडारण की आवश्यकता केवल N*sizeof(int) है, जो बहुत खराब नहीं है।

Answer 11

सॉर्टिंग फ़ंक्शंस on wikipedia की एक अच्छी सूची है जो आपको ढूंढने में मदद कर सकती है कि आप किस प्रकार के सॉर्टिंग फ़ंक्शन के बाद हैं।

उदाहरण के लिए, अपने विशिष्ट प्रश्न को संबोधित करने के लिए, ऐसा लगता है कि एक जगह में मर्ज सॉर्ट आप चाहते हैं।

हालांकि, आप strand sort पर भी एक नज़र डालना चाहते हैं, इसे कुछ बहुत ही रोचक गुण मिल गए हैं।

Answer 12

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

सूची को विभाजित करके और यह सुनिश्चित करने के लिए कि बाएं सूची को क्रमबद्ध किया गया है, वही मान बाएं हो जाते हैं और सही सूची को क्रमबद्ध किया जाता है, इसलिए वही मान सही हो जाते हैं, इस प्रकार कोई अतिरिक्त अतिरिक्त लागत के लिए स्थिरता स्थिर नहीं होगी। इसके अलावा, चूंकि यह स्वैपिंग के बजाए असाइनमेंट के साथ सौदा करता है, मुझे लगता है कि गति केवल एक ही लिखने के बाद सरणी पर त्वरित प्रकार की तुलना में थोड़ा बेहतर हो सकती है।

तो निष्कर्ष में, अपने सभी आइटम की सूची और एक सूची

Answer 13

मैं एक stable in-place quicksort और एक stable in-place merge sort को लागू किया है पर quicksort चलाते हैं। मर्ज सॉर्ट थोड़ा तेज़ है, और ओ (एन * लॉग (एन)^2) में काम करने की गारंटी है, लेकिन क्विकॉर्ट नहीं। दोनों ओ (लॉग (एन)) अंतरिक्ष का उपयोग करें।