Найди ошибку: плохие сравнения. Часть 4


Еще один простой случай. Я хочу «отсортировать» список случайным образом. Этого можно добиться путем получения случайного результата сравнения двух элементов: являются ли они больше, меньше или они равны друг другу.

myList.Sort((x, y) => (new Random()).Next(-1, 2));

Этот код генерирует случайным образом -1, 0 или 1 для каждой операции сравнения, так ведь? И мы отсортируем список случайным образом, верно?

.

.

.

.

.

.

.

В этом коде есть ряд ошибок. Во-первых, очевидно, что он нарушает все наши правила функций сравнения. Он не обеспечивает полную упорядоченность, и он может вначале выдать, что два конкретных элемента равны, а затем определить, что они вдруг стали не равными. При наличии таких некорректных функций сравнения, алгоритм сортировки может попасть в бесконечный цикл или «упасть» с ошибкой. И на самом деле, некоторые алгоритмы сортировки определяют такой вид ошибок и если они определяют, что функция сравнения является непоследовательной, генерируют исключение.

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

Перемешивание – это не сортировка; это нечто противоположное, так что не нужно использовать для этого сортировку. Существует множество эффективных алгоритмов перемешивания элементов, которые легко реализовать.

Оригинал статьи

Comments (0)

Skip to main content