मैं तारों की सरणी कैसे क्रमबद्ध कर सकता हूं?

Question

मेरे पास अल्पविराम से अलग इनपुट शब्दों की एक सूची है। मैं इन शब्दों को वर्णानुक्रम और लंबाई से क्रमबद्ध करना चाहता हूं। बिल्ट-इन सॉर्टिंग फ़ंक्शंस का उपयोग किये बिना मैं इसे कैसे कर सकता हूं?

Answer 1

अच्छा सवाल !! सॉर्टिंग शायद आने वाले कंप्यूटर वैज्ञानिक के रूप में सीखने के लिए सबसे महत्वपूर्ण अवधारणा है।

वास्तव में सूची को सॉर्ट करने के लिए बहुत से अलग एल्गोरिदम हैं।

जब आप उन सभी एल्गोरिदम को तोड़ते हैं, तो सबसे मौलिक ऑपरेशन सूची में दो वस्तुओं की तुलना है, जो उनके "प्राकृतिक आदेश" को परिभाषित करता है।

उदाहरण के लिए, आदेश पूर्णांकों की एक सूची को सॉर्ट करने में, मैं एक समारोह है कि मुझसे कहता है, यह देखते हुए किसी भी दो पूर्णांकों एक्स और वाई चाहे एक्स की तुलना में कम, के बराबर, या वाई

से अधिक है आवश्यकता होगी

अपने तारों के लिए, आपको एक ही चीज़ की आवश्यकता होगी: एक फ़ंक्शन जो आपको बताता है कि तारों में से कौन सा "कम" या "बड़ा" मान है, या वे बराबर हैं।

परंपरागत रूप से, इन "तुलनित्र" कार्यों कुछ इस तरह दिखाई:

int CompareStrings(String a, String b) { 
    if (a < b) 
     return -1; 
    else if (a > b) 
     return 1; 
    else 
     return 0; 
} 

मैं बाहर छोड़ दिया है विवरण (जैसे, आप कैसे की गणना करते हैं कि क्या एक से कम या ख से अधिक है में से कुछ सुराग? : पात्रों के माध्यम से पुनरावृत्त), लेकिन यह किसी भी तुलना समारोह का मूल कंकाल है। यदि पहला तत्व छोटा है और पहले तत्व अधिक होने पर शून्य से अधिक मान शून्य से कम मान देता है, तो तत्वों के बराबर मान होने पर शून्य लौटाया जाता है।

लेकिन सॉर्टिंग के साथ उसे क्या करना है?

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

प्रत्येक एल्गोरिदम यह गारंटी देने के लिए एक बड़ी तस्वीर रणनीति की तरह है कि कोई भी इनपुट सही तरीके से सॉर्ट किया जाएगा। यहाँ एल्गोरिदम कि आप शायद जानते हैं चाहता हूँ के कुछ ही रहे के बारे में:

बुलबुला क्रमबद्ध करें:

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

नोट: यह आमतौर पर सूची को सॉर्ट करने का एक बहुत ही प्रभावी तरीका नहीं है, क्योंकि सबसे बुरे मामलों में, एन तत्वों की सूची के लिए आपको एन बार जितनी बार संपूर्ण सूची स्कैन करने की आवश्यकता हो सकती है।

मर्ज क्रमबद्ध करें:

यह एक सूची को क्रमबद्ध करने के लिए सबसे लोकप्रिय विभाजन और जीत एल्गोरिदम में से एक है। मूल विचार यह है कि, यदि आपके पास पहले से क्रमबद्ध सूचियां हैं, तो उन्हें मर्ज करना आसान है। बस प्रत्येक सूची की शुरुआत से शुरू करें और जो भी सूची में सबसे छोटा प्रारंभिक मूल्य है, उसका पहला तत्व हटा दें। इस प्रक्रिया को तब तक दोहराएं जब तक आप दोनों सूचियों से सभी वस्तुओं का उपभोग नहीं करते हैं, और फिर आप कर लेंगे!

1  4  8  10  
    2  5 7  9 
------------ becomes ------------> 
1 2 4 5 7 8 9 10 

लेकिन यदि आपके पास दो क्रमबद्ध सूचियां नहीं हैं तो क्या होगा? क्या होगा यदि आपके पास सिर्फ एक सूची है, और इसके तत्व यादृच्छिक क्रम में हैं?

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

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

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

---

उन एक सूची छँटाई के लिए सिर्फ दो एल्गोरिदम रहे हैं, लेकिन अन्य रोचक तकनीकों का एक बहुत देखते हैं, अपने स्वयं के फायदे और नुकसान के साथ प्रत्येक: त्वरित क्रमबद्ध, मूलांक क्रमबद्ध, चयन क्रमबद्ध, ढेर क्रमबद्ध, शैल क्रमबद्ध, और बाल्टी सॉर्ट करें।

इंटरनेट सॉर्टिंग के बारे में दिलचस्प जानकारी के साथ बह रहा है। यहाँ एक अच्छी जगह शुरू करने के लिए है:

http://en.wikipedia.org/wiki/Sorting_algorithms

Answer 2

sorting algorithms के आसपास निर्मित अध्ययन का एक पूरा क्षेत्र है। आप एक साधारण चुनना और इसे लागू करना चाहते हैं।

हालांकि यह सबसे अधिक प्रदर्शनकारी नहीं होगा, इसे bubble sort को लागू करने में आपको बहुत लंबा समय नहीं लेना चाहिए।

Answer 3

एक कंसोल एप्लिकेशन बनाएं और इसे कक्षा.c के रूप में Program.cs में पेस्ट करें।

public static void Main(string[] args) 
{ 
    string [] strList = "a,b,c,d,e,f,a,a,b".Split(new [] { ',' }, StringSplitOptions.RemoveEmptyEntries); 

    foreach(string s in strList.Sort()) 
     Console.WriteLine(s); 
} 

public static string [] Sort(this string [] strList) 
{ 
    return strList.OrderBy(i => i).ToArray(); 
} 

सूचना है कि मैं प्रयोग करते हैं एक, विधि में बनाया OrderBy। जैसा कि अन्य उत्तरों बताते हैं कि वहां कई अलग-अलग प्रकार के एल्गोरिदम हैं जिन्हें आप कार्यान्वित कर सकते हैं और मुझे लगता है कि मेरे कोड स्निपेट वास्तविक प्रकार एल्गोरिदम को छोड़कर आपके लिए सब कुछ करता है।

Some C# specific sorting tutorials

Answer 4

आप निर्माण-कार्यों में उपयोग करने के लिए नहीं करना चाहते हैं, तो आप अपने आप से एक बनाने के लिए किया है। मैं बबल सॉर्ट या कुछ समान एल्गोरिदम की अनुशंसा करता हूं। बबल प्रकार एक प्रभावी एल्गोरिदम नहीं है, लेकिन यह काम करता है, और समझने में आसान है।

आपको wikipedia पर बहुत अच्छी पढ़ाई मिल जाएगी।

Answer 5

मैं quicksort के लिए विकी करने की सलाह दूंगा।

अभी भी सुनिश्चित नहीं है कि आप अंतर्निहित प्रकार का उपयोग क्यों नहीं करना चाहते हैं?

Answer 6

बुलबुला तरह नुकसान मस्तिष्क।

निवेशन तरह कम से कम के रूप में समझते हैं और कोड के लिए सरल है, और वास्तव में व्यवहार में (बहुत छोटे डेटा सेट, और लगभग-छाँटे गए डेटा के लिए) उपयोगी है। यह इस तरह से काम करता है:

मान लीजिए कि पहले n आइटम क्रम में पहले से ही कर रहे हैं (आप, n = 1 के साथ शुरू कर सकते हैं के बाद से अपने आप ही स्पष्ट रूप से एक बात "सही क्रम में" है)।

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

अब पहली n + सरणी में 1 आइटम, क्रम में हैं क्योंकि धुरी सब कुछ यह की तुलना में छोटे के अधिकार के लिए है, और सब कुछ इसे से भी बड़ा के बाईं ओर। चूंकि आपने क्रम में एन वस्तुओं के साथ शुरुआत की है, यह प्रगति है।

दोहराएं, प्रत्येक चरण में 1 तक बढ़ने के साथ, जब तक आप पूरी सूची संसाधित नहीं कर लेते।

यह एक तरीका है कि आप शारीरिक रूप से क्रम में किसी अलमारी में फ़ोल्डर्स की एक श्रृंखला डाल सकता है से मेल खाती है: में एक डाल; फिर कमरे को बनाने के लिए एक स्थान से इसके बाद की हर चीज को दबाकर दूसरी स्थिति को अपनी सही स्थिति में डाल दें; समाप्त होने तक दोहराना। कोई भी कभी भी भौतिक वस्तुओं को बबल प्रकार से नहीं करता है, इसलिए यह मेरे लिए एक रहस्य है कि इसे "सरल" क्यों माना जाता है।

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

Answer 7

उपयोग NSort

मैं किताब Windows Developer Power Tools में कुछ साल पहले NSort पुस्तकालय भर में भाग गया। एनएसओआरटी लाइब्रेरी कई सॉर्टिंग एल्गोरिदम लागू करता है। अपने स्वयं के सॉर्टिंग लिखने पर एनएसओआर जैसे कुछ का उपयोग करने का मुख्य लाभ यह है कि पहले से ही परीक्षण और अनुकूलित किया गया है।सी # में तेजी से स्ट्रिंग सॉर्ट कोड को

Answer 8

पोस्टिंग लिंक:

http://www.codeproject.com/KB/cs/fast_string_sort.aspx

एक और मुद्दा: सुझाव तुलनित्र ऊपर गैर अंग्रेजी भाषाओं के लिए अनुशंसित नहीं है:

पूर्णांक CompareStrings (स्ट्रिंग एक, स्ट्रिंग बी) {
अगर (< बी) वापसी -1;
अन्य यदि (ए> बी)
वापसी 1; अन्य
वापसी 0; }

चेकआउट गैर-अंग्रेज़ी भाषा प्रकार के लिए इस लिंक:

http://msdn.microsoft.com/en-us/goglobal/bb688122

और उल्लेख किया है, उपयोग वास्तव में विशाल सरणियों कि स्मृति में फिट नहीं है के लिए nsort के रूप में।