सूची <T> क्यों है। विधि विधि बराबर IComparable <T> तत्वों को पुन: व्यवस्थित करता है?

Question

मुझे समस्या है कि सूची सॉर्ट विधि सॉर्टिंग के साथ कैसे काम करती है। निम्नलिखित तत्व को देखते हुए:

class Element : IComparable<Element> 
{ 
    public int Priority { get; set; } 
    public string Description { get; set; } 

    public int CompareTo(Element other) 
    { 
     return Priority.CompareTo(other.Priority); 
    } 
} 

अगर मैं इसे इस तरह सुलझाने की कोशिश:

List<Element> elements = new List<Element>() 
          { 
           new Element() 
            { 
             Priority = 1, 
             Description = "First" 
            }, 
           new Element() 
            { 
             Priority = 1, 
             Description = "Second" 
            }, 
           new Element() 
            { 
             Priority = 2, 
             Description = "Third" 
            } 
          }; 
elements.Sort(); 

तो पहला तत्व पहले से दूसरा तत्व "दूसरा" है। या, दूसरे शब्दों में, इस दावे विफल रहता है:

Assert.AreEqual("First", elements[0].Description); 

क्यों नेट मेरी सूची को पुन: क्रम है जब तत्व मूलतः एक ही हैं? अगर मैं तुलना गैर-शून्य मान देता हूं तो मैं केवल सूची को पुन: व्यवस्थित करना चाहता हूं।

Answer 1

MSDN से विधि List.Sort() के प्रलेखन से:

इस विधि Array.Sort, जो quicksort एल्गोरिथ्म का उपयोग करता उपयोग करता है। यह कार्यान्वयन एक अस्थिर प्रकार का प्रदर्शन करता है; यानी, यदि दो तत्व बराबर हैं, तो उनके आदेश को संरक्षित नहीं किया जा सकता है। इसके विपरीत, एक स्थिर प्रकार बराबर तत्वों के क्रम को संरक्षित करता है। http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx

अनिवार्य रूप से, प्रकार के रूप में बनाया गया है और दस्तावेज प्रदर्शन कर रहा है:

यहाँ लिंक है।

Answer 2

आपने बताया कि चीजों की तुलना कैसे करें और ऐसा किया। आपको अपने आवेदन में क्रमबद्ध करने के आंतरिक कार्यान्वयन पर भरोसा नहीं करना चाहिए। यही कारण है कि आप तुलनात्मक को ओवरराइड करते हैं। यदि आप माध्यमिक क्रम पैरामीटर (इस मामले में "विवरण") चाहते हैं, तो इसे अपने तुलना में कोड करें। काम करने के लिए बस क्रमबद्ध कैसे होता है इस पर निर्भर करते हुए एक बग में कोड करने का एक शानदार तरीका है जो खोजने में बहुत मुश्किल है।

आप .NET के लिए एक स्थिर Quicksort पा सकते हैं या merge sort (जो पहले से ही स्थिर है) का उपयोग कर सकते हैं।

Answer 3

आप अपनी संरचना में "इंडेक्स वैल्यू" जोड़कर इसे ठीक कर सकते हैं, और तुलनात्मक विधि में जब प्राथमिकता। कॉम्पारे 0 लौटाता है तो आपको इसे क्रमबद्ध करने से पहले "इंडेक्स" मान प्रारंभ करना होगा।

compareTo विधि इस प्रकार दिखाई देगा:

public int CompareTo(Element other) 
{ 
    var ret = Priority.CompareTo(other.Priority); 
    if (ret == 0) 
    { 
     ret = Comparer<int>.Default.Compare(Index, other.Index); 
    } 
    return ret; 
} 

तो बजाय elements.Sort() करने का, आप क्या करेंगे:

for(int i = 0; i < elements.Count; ++i) 
{ 
    elements[i].Index = i; 
} 
elements.Sort(); 

Answer 4

क्यों List.Sort() अस्थिर है के लिए अन्य प्रतिसाद देखें। यदि आपको एक स्थिर प्रकार की आवश्यकता है और .NET 3.5 का उपयोग कर रहे हैं, तो Enumerable.OrderBy() (LINQ) आज़माएं।

Answer 5

आप एक के बजाय दो क्षेत्रों आप ऐसा कर सकता है के आधार पर सॉर्ट करने के लिए करना चाहता था, तो:

class Element : IComparable<Element> 
{ 
    public int Priority { get; set; } 
    public string Description { get; set; } 

    public int CompareTo(Element other) 
    { 
     if (Priority.CompareTo(other.Priority) == 0) 
     { 
      return Description.CompareTo(other.Description); 
     } else { 
      return Priority.CompareTo(other.Priority); 
     } 
    } 
} 

जाहिर है, यह एक स्थिर खोज एल्गोरिथ्म के आवश्यकता को पूरा नहीं करता है; हालांकि, यह आपके दावे को पूरा करता है, और समानता की स्थिति में आपके तत्व के आदेश पर नियंत्रण की अनुमति देता है।

Answer 6

यहाँ List<T> where T : IComparable<T> के लिए एक विस्तार विधि SortStable() है:

public static void SortStable<T>(this List<T> list) where T : IComparable<T> 
{ 
    var listStableOrdered = list.OrderBy(x => x, new ComparableComparer<T>()).ToList(); 
    list.Clear(); 
    list.AddRange(listStableOrdered); 
} 

private class ComparableComparer<T> : IComparer<T> where T : IComparable<T> 
{ 
    public int Compare(T x, T y) 
    { 
     return x.CompareTo(y); 
    } 
} 

टेस्ट:

[Test] 
public void SortStable() 
{ 
    var list = new List<SortItem> 
        { 
         new SortItem{ SortOrder = 1, Name = "Name1"}, 
         new SortItem{ SortOrder = 2, Name = "Name2"}, 
         new SortItem{ SortOrder = 2, Name = "Name3"}, 
        }; 

    list.SortStable(); 

    Assert.That(list.ElementAt(0).SortOrder, Is.EqualTo(1)); 
    Assert.That(list.ElementAt(0).Name, Is.EqualTo("Name1")); 
    Assert.That(list.ElementAt(1).SortOrder, Is.EqualTo(2)); 
    Assert.That(list.ElementAt(1).Name, Is.EqualTo("Name2")); 
    Assert.That(list.ElementAt(2).SortOrder, Is.EqualTo(2)); 
    Assert.That(list.ElementAt(2).Name, Is.EqualTo("Name3")); 
} 

private class SortItem : IComparable<SortItem> 
{ 
    public int SortOrder { get; set; } 
    public string Name { get; set; } 

    public int CompareTo(SortItem other) 
    { 
     return SortOrder.CompareTo(other.SortOrder); 
    } 
} 

परीक्षा पद्धति में, यदि आप फोन क्रमबद्ध() SortStable() के बजाय विधि, आप देख सकते हैं कि परीक्षण असफल हो जाएगा।

Answer 7

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

जावा या नेट जैसे ढांचे के तहत उपयोग किए जाने वाले सॉर्ट विधियों का व्यावहारिक रूप से अधिक उपयोग हो सकता है एक सी qsor में स्वीकार्य से अधिक अस्थायी भंडारण किया जाएगा टी() दिनचर्या। क्रमबद्ध करने के लिए सरणी के आकार के बराबर एक अस्थायी स्मृति आवश्यकता किसी भी विशेष समस्या को उत्पन्न नहीं करती है। फिर भी, चूंकि लाइब्रेरीज़ के लिए क्विक्सोर्ट कार्यान्वयन की आपूर्ति करना पारंपरिक है, ऐसा लगता है कि .NET के बाद पैटर्न होता है।