#c# #arrays #sorting
#c# #массивы #сортировка
Вопрос:
Я пытаюсь решить 11321 — Sort! Сортировка!! и сортировка!!!используя C #, напрямую переводя мои решения (а также решения других людей) с cpp и Java.
Моя проблема в том, что listName.Sort() or Array.Sort(listName, ...Comparer.Create()...) неправильно сортирует выходные данные во время первого прохода. Я должен вызвать его дважды, чтобы иметь возможность правильно отсортировать его.
В некоторых случаях я вручную устанавливаю точки останова внутри compareTo() при вызове Array.Sort, добавляю ссылку на список внутри замыкания специально, чтобы я мог наблюдать за значениями по мере сортировки, и они сортируются правильно до тех пор, пока не вернется метод Array.Sort(), в котором я вижунекоторые значения возвращаются в неправильном порядке.
Я использую тестовые примеры Morass из uDebug для тестирования, и один пример неправильного результата сортировки, который я получаю, находится в строке 10919 вывода:
Accepted My Output
10919 457 10919 461
10920 461 10920 457
Как вы можете видеть, числа 461 и 457 должны быть отсортированы в порядке возрастания их значения по модулю 500, что равно 461 и 457 соответственно. Если я снова вызову метод сортировки во второй раз в моем коде ниже, то я, наконец, получу правильный вывод.
Я думаю, мой вопрос в том, почему это происходит? Что-то не так с моей реализацией? Мои реализации представляют собой почти переводы 1 к 1 принятого кода Java или cpp. Обратите внимание, что я также пытался использовать LINQ OrderBy() , который выдает разные результаты, но в конечном итоге правильный, если вызывается достаточно раз.
У меня есть следующий класс Number с соответствующей реализацией IComparable:
class Number : IComparable<Number>
{
public int Value { get; }
public int Mod { get; }
public bool IsOdd { get; }
public Number(int val, int mod)
{
Value = val;
Mod = mod;
IsOdd = val % 2 != 0;
}
public int CompareTo(Number other)
{
var leftVal = Value;
var leftMod = Mod;
var rightVal = other.Value;
var rightMod = other.Mod;
var leftOdd = IsOdd;
var rightOdd = other.IsOdd;
if (leftMod < rightMod) return -1;
else if (leftMod > rightMod) return 1;
else
{
if (leftOdd amp;amp; rightOdd)
{
return leftVal > rightVal ? -1 : 1;
}
else if (!leftOdd amp;amp; !rightOdd)
{
return leftVal > rightVal ? 1 : -1;
}
else if (leftOdd)
{
return -1;
}
else// (rightOdd)
{
return 1;
}
}
}
}
И мой основной метод:
public static void Main(string[] args)
{
while (true)
{
var settings = Console.ReadLine().Split(' ');
var N = int.Parse(settings[0]);
var M = int.Parse(settings[1]);
if (N == 0 amp;amp; M == 0) break;
Console.WriteLine($"{N} {M}");
var output = new List<Number>();
var i = 0;
while (i < N)
{
var line = Console.ReadLine();
var val = int.Parse(line);
var mod = val % M;
output.Add(new Number(val, mod));
i ;
}
output.Sort();
// uncomment to produce acceptable answer
// output.Sort();
foreach (var line in output)
{
Console.WriteLine(line.Value);
}
}
Console.WriteLine("0 0");
}
Edit 1:
Just a note that I am redirecting stdin and stdout from a file/to a StringBuilder, so I can automate testing.
static void Main(string[] args)
{
var builder = new StringBuilder();
var output = new StringWriter(builder);
Console.SetOut(output);
var solution = File.ReadAllText("P11321_Outputs");
var problem = new StreamReader("P11321_Inputs");
Console.SetIn(problem);
P11321_1.Main(args);
}
Edit 2:
Here is a portion of the test case where the weird behavior is occurring. A concrete repro step is, if you change the test case to only have 38 items, and remove 11 from the input, then 457 and 461 sorts correctly.
Ввод:
39 500
-121
582
163
457
-86
-296
740
220
-867
-333
-773
11
-446
-259
-238
782
461
756
-474
-21
-358
593
548
-962
-411
45
-604
-977
47
-561
-647
926
578
516
382
-508
-781
-322
712
0 0
Вывод:
39 500
-977
-474
-962
-446
-411
-867
-358
-333
-322
-296
-781
-773
-259
-238
-647
-121
-604
-86
-561
-21
-508
11
516
45
47
548
578
582
593
163
712
220
740
756
782
382
926
457
461
0 0
Комментарии:
1. Этот код сортирует эти 2 числа правильно. Я полагаю, вы читаете большую выборку входных данных из файла? Опубликуйте этот код.
2. ДА. Я перенаправляю stdin и stdout из входного файла и в StringBuilder соответственно, чтобы я мог автоматизировать тестирование. Я опубликую сообщение через секунду.
3. @MarkBenningfield Вручную просматривает бумагу, она сортируется правильно. Странное поведение, с которым я столкнулся, заключалось в том, что если я изменяю тестовый пример, добавляя или удаляя несколько строк, то иногда он сортируется правильно.
Ответ №1:
Вам удалось проверить все случаи в ваших логических тестах, за исключением случаев, когда значения равны. Алгоритм сортировки должен не только знать, больше или меньше элементов друг друга, но и знать, равны ли они друг другу.
if (leftMod < rightMod)
return -1;
else if (leftMod > rightMod)
return 1;
else
{
if (leftVal == rightVal)
{
return 0; // need this so you don't orphan an element when tested against itself
}
if (leftOdd amp;amp; rightOdd)
{
return leftVal > rightVal ? -1 : 1;
}
else if (!leftOdd amp;amp; !rightOdd)
{
return leftVal > rightVal ? 1 : -1;
}
else if (leftOdd)
{
return -1;
}
else// (rightOdd)
{
return 1;
}
}
Комментарии:
1. По какой-то причине это работает. Делает массив. Сортировать сравнивать элементы с самим собой? Кроме того, ошибочным тестовым примером были 457 и 461, которые не равны и никогда не входят в это добавленное условие. Как это решило проблему, по крайней мере, для образца ввода?
2. В зависимости от алгоритма, для процедуры сортировки нет ничего необычного в сравнении элемента с самим собой. Помните, что нетривиальная процедура сортировки перемещает элементы совсем немного.
Ответ №2:
Повторяя ответ Марка Беннингфилда, я хотел бы представить доказательство концепции о том, почему важно включить равенство в реализацию пользовательского средства сравнения. Существует не только риск получения неверных результатов, но и риск никогда не получить результаты!
Попытка отсортировать только два числа (2, 1) с помощью глючного компаратора:
class BuggyComparer : IComparer<int>
{
public int Compare(int x, int y) => x < y ? -1 : 1; // Equality?
}
var source = new int[] { 2, 1 };
var sorted = source.OrderBy(n => n, new BuggyComparer());
Console.WriteLine(String.Join(", ", sorted)); // Infinite loop
Программа не завершается, поскольку сортировка не может быть завершена.