C # IComparer возвращает неожиданный результат при сравнении тех же строк

Question

У меня есть ситуация, когда все члены моего списка имеют одинаковый идентификатор (идентификатор - строка, а не целое число).В рамках бизнес-правил мне нужно отсортировать список в порядке возрастания.Моя оригинальная реализация очень похожа на ниже.Я ожидал получить неизменный список после применения сортировки, поскольку все члены списка имеют одинаковые идентификаторы, но, к моему удивлению, результат отличается.

Ниже приведен мой оригинальный список перед сортировкой.

Id: D1.2 Имя: Pachycephalosaurus
Id: D1.2 Имя: Amargasaurus
Id: D1.2 Имя: Mamenchisaurus
Id: D1.2 Имя: Deinonychus
Id: D1.2 Имя: Coelophysis
Идентификатор: D1.2 Имя: Овираптор
Идентификатор: D1.2 Имя: Тиранозавр

Сортировка с альтернативным компаратором:

Идентификатор: D1.2 Имя: Pachycephalosaurus
Id: D1.2 Имя: Oviraptor
Id: D1.2 Имя: Coelophysis
Id: D1.2 Имя: Deinonychus
Id: D1.2 Имя: Mamenchisaurus
Id: D1.2Имя: Amargasaurus
Id: D1.2 Имя: Tyrannosaur

Код

class Program
{
    static void Main(string[] args)
    {
        new ComparerIssue().MainMethod();
        Console.ReadKey();
    }
}

internal class DinoComparer : IComparer<Dinosaur>
{
    public int Compare(Dinosaur dinosaur1, Dinosaur dinosaur2)
    {
        return Compare(dinosaur1.Id, dinosaur2.Id);
    }

    private int Compare(string x, string y)
    {
        if (x == y)
        {
            return 1; //I have tried using 1 and 0; -1 throws exception
        }
        return x.CompareTo(y);
    }
}
public class ComparerIssue
{
    public void MainMethod()
    {
        List<Dinosaur> dinosaurs = new List<Dinosaur>();
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Pachycephalosaurus" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Amargasaurus" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Mamenchisaurus" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Deinonychus" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Coelophysis" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Oviraptor" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Tyrannosaur" });
        Display(dinosaurs);

        DinoComparer dc = new DinoComparer();

        Console.WriteLine("\nSort with alternate comparer:");

        dinosaurs.Sort(dc);
        Display(dinosaurs);
    }
    private static void Display(IEnumerable<Dinosaur> list)
    {
        Console.WriteLine();
        foreach (Dinosaur dinosaur in list)
        {
            Console.WriteLine("Id: " + dinosaur.Id + " Name: " + dinosaur.Name);
        }
    }
}
public class Dinosaur
{
    public string Id { get; set; }
    public string Name { get; set; }
}

Answer 1

Лично я бы использовал ответ от icesar, но вместо этого использовал бы статический string.Compare :

return string.Compare(x, y);

Это делает сравнение немного "безопаснее", вы ненужно проверять наличие нулей.

В качестве альтернативы простой оператор LINQ сделает эту работу:

myList = myList.OrderBy(p => p.ID).ThenBy(p => p.Name);

Вы также должны заметить, что сортировка по ID в виде строки приведет к ошибочным результатам, как только выполучить несколько предметов в списке;21 будет размещен до 3.Возможно, вы захотите привести его к int на каком-то этапе.

Answer 2

С MSDN :

Этот метод использует Array.Sort, который использует алгоритм QuickSort. это реализация выполняет нестабильную сортировку ; то есть, если два элемента равным образом, их порядок может не быть сохранен. В отличие от стабильного рода сохраняет порядок элементов, которые равны.

(мой акцент)

Именно это и происходит.

EDIT Как подсказали другие, вы можете использовать метод linq OrderBy , который выполняет стабильную сортировку:

var d2 = dinosaurs.OrderBy(d => d.Id).ToList();

Answer 3

Вы нарушаете контракт на IComparable; когда ваши идентификаторы равны, вы на самом деле говорите, что один больше другого (поэтому его нужно отсортировать)

Из документации :

Менее нуля Этот объект меньше, чем другой параметр. Ноль Этот объект равен другому. Больше нуля Этот объект больше других.

Альтернативная реализация для Compare будет выглядеть так:

private int Compare(string x, string y)
{
    return x.CompareTo(y);
    // There would be potential to do secondary sorts if the line above only returned zero - you'd obviously need to capture and test the result...
}

Answer 4

Вы нарушаете подразумеваемый контракт IComparer, поскольку Compare(dino1,dino2) и Compare(dino2,dino1) вернут, что dino1 больше dino2 и dino2 больше dino1. Поскольку вы не определяете порядок должным образом, результаты в лучшем случае будут "случайными".

Если вы не можете определить общий порядок, основываясь исключительно на значениях ID, то использование значений ID не может быть основой для вашей реализации IComparer.

Answer 5

Вы должны вернуть только return x.CompareTo(y); из вашего private int Compare(string x, string y) метода, поскольку вы сравниваете только на основе строк ...

Как это:

private int Compare(string x, string y)
{
    return x.CompareTo(y);
}

Надеюсь, это поможет, Иван

Answer 6

Я искренне благодарю всех за отзыв.Я реализовал стабильную сортировку, используя метод вставки, найденный в http://www.csharp411.com/c-stable-sort/.. Я включил окончательный код для справки.

internal class DinoComparer : IComparer<Dinosaur>
{
    public int Compare(Dinosaur dinosaur1, Dinosaur dinosaur2)
    {
        return Compare(dinosaur1.Id, dinosaur2.Id);
    }

    private int Compare(string x, string y)
    {
        return x.CompareTo(y);
    }
}
public class ComparerIssue
{
    public void MainMethod()
    {
        List<Dinosaur> dinosaurs = new List<Dinosaur>();
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Pachycephalosaurus" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Amargasaurus" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Mamenchisaurus" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Deinonychus" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Coelophysis" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Oviraptor" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Tyrannosaur" });
        Display(dinosaurs);

        //Console.WriteLine("\nSort with unstable comparer:");
        //dinosaurs.Sort(new DinoComparer());

        Console.WriteLine("\nSort with stable comparer:");
        dinosaurs = (List<Dinosaur>)InsertionSort.Sort(dinosaurs, new DinoComparer().Compare);

        Display(dinosaurs);
    }
    private static void Display(IEnumerable<Dinosaur> list)
    {
        Console.WriteLine();
        foreach (Dinosaur dinosaur in list)
        {
            Console.WriteLine("Id: " + dinosaur.Id + " Name: " + dinosaur.Name);
        }
    }
}
public class Dinosaur
{
    public string Id { get; set; }
    public string Name { get; set; }
}
public class InsertionSort
{
    public static IList<T> Sort<T>(IList<T> list, Comparison<T> comparison)
    {
        if (list == null)
            throw new ArgumentNullException("list");
        if (comparison == null)
            throw new ArgumentNullException("comparison");

        int count = list.Count;
        for (int j = 1; j < count; j++)
        {
            T key = list[j];

            int i = j - 1;
            for (; i >= 0 && comparison(list[i], key) > 0; i--)
            {
                list[i + 1] = list[i];
            }
            list[i + 1] = key;
        }
        return list;
    }
}

Answer 7

К сожалению, насколько я знаю, в Frameworks не реализован метод стабильной сортировки. Тебе придется сделать это самому.

Это http://www.csharp411.com/c-stable-sort/ хороший пример метода стабильной сортировки.