कौन सा सॉर्टिंग एल्गोरिदम लगभग पूरी तरह से क्रमबद्ध सूची को फिर से क्रमबद्ध करने के लिए सबसे उपयुक्त है?

Question

मेरे पास स्ट्रिंग्स की एक सूची है जिसे एक विशिष्ट तुलना फ़ंक्शन द्वारा क्रमबद्ध किया गया है।

अब मुझे विभिन्न तुलना फ़ंक्शन का उपयोग करके इस सूची को फिर से क्रमबद्ध करना होगा।

उदाहरण के लिए उमलॉट्स जैसे कुछ विशेष पात्रों की तुलना करते समय यह नया तुलना फ़ंक्शन थोड़ा अलग व्यवहार करता है। ज्यादातर मामलों में तत्व को सही स्थिति में जाने के लिए केवल एक या दो स्लॉट ले जाया जाना चाहिए।

कौन सा सॉर्टिंग एल्गोरिदम रनटाइम निष्पादन गति के मामले में लगभग पूरी तरह क्रमबद्ध सूची को पुन: क्रमबद्ध करने के लिए सबसे उपयुक्त है?

Answer 1

Insertion sort छोटी या लगभग क्रमबद्ध सूचियों पर अच्छी तरह से काम करता है।

इस ACM Paper से: सूची लंबाई और छोटे sortedness अनुपात की विभिन्न संयोजनों की अनियमित रूप से उत्पन्न सूचियों पर

टेस्ट संकेत मिलता है कि सीधे निवेशन छोटे या बहुत करीब क्रमबद्ध सूचियों और उस के लिए है क्रमबद्ध सबसे अच्छा क्विकर्सोर्ट अन्यथा सर्वोत्तम है।

विकी लेख Insertion sort से:

इनपुट सरणी पहले से ही हल कर रहा है, तो प्रविष्टि प्रकार के रूप में कुछ के रूप में n-1 तुलना करता है, इस प्रकार प्रविष्टि तरह अधिक कुशल जब दी बनाने अनुसार क्रमबद्ध या "लगभग क्रमबद्ध" सरणी।

तो सवाल: Is there ever a good reason to use Insertion Sort?

Answer 2

दोनों खोज संचालन के लिए उपयोग है? यदि हां, तो आप पहले सॉर्टिंग प्रक्रिया के दौरान कुछ हैश पेड़ का निर्माण कर सकते हैं और इसे अन्य प्रकार के संचालन के लिए उपयोग कर सकते हैं

Answer 3

जैसा कि मैंने समझा है कि आपकी डेटा सूची पहले से ही क्रमबद्ध है (एएससीआई/देश वर्णसेट ऑर्डर द्वारा कहें), लेकिन कुछ शब्दकोश नियमों के बिना विशेष देश के लिए आवेदन किया। उदाहरण जर्मनी और उनके Umlauts लिए

विकिपीडिया

आप नए आइटम डालने नहीं कर रहे हैं में Germanic_umlaut देखते हैं, तो आप सिर्फ थोड़ा और अधिक सख्त छंटाई नियम से उन्हें सहारा करना चाहते हैं।

के रूप में आप यहाँ

http://www.softpanorama.org/Algorithms/Sorting/bubblesort.shtml

बुलबुला तरह बस कुछ ही क्रमपरिवर्तन साथ allready अनुसार क्रमबद्ध सूची पर अच्छी तरह से काम उदाहरण के लिए पढ़ सकते हैं। यह लगता है कि बबल प्रकार के साथ शुरू करने के लिए अच्छा एल्गोरिदम है। यह भी ध्यान रखें कि बबल प्रकार "स्थिर" सॉर्टिंग एल्गोरिदम है। यह आपके परिदृश्य के लिए महत्वपूर्ण हो सकता है।

Answer 4

लगभग क्रमबद्ध सूचियों के लिए, Comb की विविधताएं Quicksort से बेहतर प्रदर्शन करती हैं। मैंने यह देखने के लिए परीक्षण नहीं किया है कि कैसे कंघी सॉर्ट सम्मिलन प्रकार से तुलना करता है।