목록 .sort 메소드가 동일한 icomparty 요소를 재정렬하는 이유는 무엇입니까?

StackOverflow https://stackoverflow.com/questions/800007

  •  03-07-2019
  •  | 
  •  

문제

목록 정렬 메소드가 정렬을 처리하는 방법에 문제가 있습니다. 다음 요소가 주어지면 :

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);

요소가 본질적으로 동일 할 때 .NET이 내 목록을 재정렬하는 이유는 무엇입니까? 비교가 0이 아닌 값을 반환하는 경우 목록 만 재정렬하기를 원합니다.

도움이 되었습니까?

해결책

msdn의 list.sort () 메소드의 문서에서 :

이 방법은 QuickSort 알고리즘을 사용하는 Array.Sort를 사용합니다. 이 구현은 불안정한 종류를 수행합니다. 즉, 두 요소가 같으면 순서가 보존되지 않을 수 있습니다. 대조적으로, 안정적인 정렬은 동일한 요소의 순서를 보존합니다.

다음은 링크입니다.http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx

본질적으로, 정렬은 설계 및 문서화 된대로 수행됩니다.

다른 팁

다음은 확장 메소드 Sortstable ()을위한 것입니다 List<T> where T : IComparable<T>:

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 () 대신 Sort () 메소드를 호출하면 테스트가 실패 할 수 있습니다.

당신은 그것을 비교하는 방법을 말했고 그랬습니다. 응용 프로그램에서 내부 구현에 의존해서는 안됩니다. 그렇기 때문에 비교를 무시할 수 있습니다. 보조 정렬 매개 변수 (이 경우 "설명")가 원한다면 비교로 코딩하십시오. Sort가 작동하는 방식에 의존하는 것은 찾기가 매우 어려운 버그로 코딩하는 좋은 방법입니다.

.NET 용 안정적인 퀵 소트를 찾거나 정렬을 병합하십시오 (이미 안정적입니다).

List.Sort ()가 불안정 한 이유에 대한 다른 응답을 참조하십시오. 안정적인 정렬이 필요하고 .NET 3.5를 사용하는 경우 시도하십시오. enumerable.orderby () (LINQ).

구조에 "인덱스 값"을 추가하고 Priority.compareto가 0을 반환하는 경우 비교 방법에 해당 사항을 포함 하여이 문제를 해결할 수 있습니다. 그러면 정렬을 수행하기 전에 "색인"값을 초기화해야합니다.

비교 방법은 다음과 같습니다.

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();

일부 응용 프로그램에서, 일부 기준에 따라 항목 목록이 정렬 될 때, 동일을 비교하는 원래 항목 순서는 불필요합니다. 다른 응용 프로그램에서는 필요합니다. 일치하는 키가있는 항목의 배열을 보존하는 정렬 방법 ( "안정적인 종류"라고 불리는 것은 일반적으로 ( "불안정한 종류") 또는 다른 양의 임시 저장소가 필요하지 않은 것보다 훨씬 느립니다 (그리고 여전히 다소 느린다. ). 널리 퍼지는 첫 번째 "표준 라이브러리"정렬 루틴은 아마도 qsort() 표준 C 라이브러리에 포함 된 기능. 이 라이브러리는 종종 사용 가능한 총 메모리 양에 비해 큰 목록을 정렬하는 데 사용되었을 것입니다. 배열의 항목 수에 비례하는 임시 저장량이 필요한 경우 라이브러리는 훨씬 덜 유용했을 것입니다.

Java 또는 .NET와 같은 프레임 워크에서 사용될 정렬 방법은 C QSORT () 루틴에서 수용 가능한 것보다 훨씬 더 많은 임시 스토리지를 사용할 수 있습니다. 정렬 할 배열의 크기와 동일한 임시 메모리 요구 사항은 대부분의 경우 특정 문제를 제기하지 않습니다. 그럼에도 불구하고 라이브러리가 QuickSort 구현을 제공하는 것이 전통적이기 때문에 .NET이 뒤 따르는 패턴 인 것 같습니다.

두 분야 대신 두 개의 필드를 기준으로 정렬하려면 다음을 수행 할 수 있습니다.

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);
        }
    }
}

분명히 이것은 안정적인 검색 알고리즘의 요구 사항을 충족시키지 못합니다. 그러나 그것은 당신의 주장을 충족시키고 평등의 경우 요소 순서를 제어 할 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top