मैं इन सॉर्टिंग एल्गोरिदम का उपयोग किस स्थितियों में करता हूं?

Question

मैं इन एल्गोरिदम के अधिकांश के लिए कार्यान्वयन पता है, लेकिन मैं उनके लिए क्या उपयोग करने के लिए सेट डेटा आकार के लिए पता नहीं है (और डेटा शामिल है):

1. मर्ज क्रमबद्ध
2. बुलबुला क्रमबद्ध (मुझे पता है , नहीं बहुत बार)
3. त्वरित क्रमबद्ध
4. निवेशन क्रमबद्ध
5. चयन क्रमबद्ध
6. मूलांक क्रमबद्ध

Answer 1

सबसे पहले, आप सभी छँटाई एल्गोरिदम एक O(n2) जटिलता है और उन्हें दूर फेंक देते हैं कि ले।

फिर, आप अपने छँटाई एल्गोरिदम के कई proprieties का अध्ययन करने और तय करें कि उनमें से हर एक बेहतर समस्या को हल करने के लिए अनुकूल हो जाएगा करने के लिए है। सबसे अधिक महत्वपूर्ण हैं:

यथा-स्थान एल्गोरिथ्म है? इसका मतलब है कि सॉर्टिंग एल्गोरिदम किसी भी (O(1) वास्तव में) अतिरिक्त मेमोरी का उपयोग नहीं करता है। जब आप स्मृति-महत्वपूर्ण अनुप्रयोग चला रहे हों तो यह स्वामित्व बहुत महत्वपूर्ण है।

बुलबुला-तरह, निवेशन-तरह और चयन-तरह निरंतर स्मृति का उपयोग करें। मर्ज-सॉर्ट के लिए एक इन-प्लेस संस्करण भी है।

क्या एल्गोरिदम स्थिर है? इसका मतलब है कि यदि दो तत्व x और y आपकी तुलना विधि के बराबर हैं, और इनपुट xy से पहले पाया जाता है, तो आउटपुट xy से पहले मिलेगा।

मर्ज-सॉर्ट, बबल-सॉर्ट और सम्मिलन-प्रकार स्थिर हैं।

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

अधिक जानकारी here।

Answer 2

1. अतिरिक्त स्थान सरणी के आकार के बराबर का उपयोग करते समय एक मुद्दा
2. केवल बहुत छोटे डेटा पर सेट
3. जब आप चाहते हैं एक में जगह तरह और एक स्थिर प्रकार की आवश्यकता नहीं है नहीं है
4. केवल बहुत छोटे डेटा सेट पर, या यदि सरणी की बड़ी संभावना है पहले से ही
5. केवल पर बहुत छोटे डेटा सेट क्रमबद्ध करना
6. जब आइटम की संख्या को मानों की श्रेणी अनुपात छोटा है (प्रयोग का सुझाव दिया)

ध्यान दें कि आमतौर पर मर्ज या त्वरित सॉर्ट कार्यान्वयन subroutine के हिस्सों के लिए सम्मिलन प्रकार का उपयोग करते हैं जहां उप-सरणी बहुत छोटी होती है।

Answer 3

उपयोग बुलबुला केवल क्रमबद्ध जब डेटा क्रमबद्ध करना ड्रम मेमरी घूर्णन पर संग्रहीत है।यह उस उद्देश्य के लिए इष्टतम है, लेकिन यादृच्छिक-पहुंच स्मृति के लिए नहीं। इन दिनों, यह "बबल सॉर्ट का उपयोग न करें" की मात्रा है।

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

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

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

आम तौर पर आप "सादा" त्वरित सॉर्ट का उपयोग नहीं करते हैं, क्योंकि पिवॉट्स की बुद्धिमान पसंद के साथ भी इसमें Omega(n^2) सबसे खराब मामला है लेकिन सम्मिलन सॉर्ट के विपरीत इसमें कोई उपयोगी सर्वोत्तम मामला नहीं है। "हत्यारा" मामलों को व्यवस्थित रूप से बनाया जा सकता है, इसलिए यदि आप "अविश्वसनीय" डेटा को सॉर्ट कर रहे हैं तो कुछ उपयोगकर्ता जानबूझ कर अपने प्रदर्शन को मार सकते हैं, और वैसे भी कुछ डोमेन-विशिष्ट कारण हो सकते हैं कि आपका डेटा हत्यारा के मामलों के लिए क्यों अनुमानित है। यदि आप यादृच्छिक पिट्स चुनते हैं तो हत्यारा के मामलों की संभावना नगण्य है, इसलिए यह एक विकल्प है, लेकिन सामान्य दृष्टिकोण "IntroSort" है - एक क्विकॉर्ट जो खराब मामलों का पता लगाता है और हीपॉर्ट में स्विच करता है।

मूलांक क्रमबद्ध एक oddball का एक सा है। यह आम समस्याओं जिसके लिए यह सबसे अच्छा है खोजने के लिए मुश्किल है, लेकिन यह निश्चित-चौड़ाई डेटा के लिए अच्छा asymptotic सीमा (O(n), जहां तुलना प्रकार Omega(n log n) कर रहे हैं) है। यदि आपका डेटा निश्चित-चौड़ाई है, और इनपुट संभावित मानों की संख्या से बड़ा है (उदाहरण के लिए, 4 बिलियन 32-बिट पूर्णांक से अधिक) तो वहां एक मौका होना शुरू हो जाता है कि कुछ प्रकार के रेडिक्स सॉर्ट अच्छा प्रदर्शन करेंगे।