Может ли List.Sort с использованием рандомизированного делегата сравнения работать бесконечно?

Question

Я исследую и тестирую производительность различных способов рандомизации упорядоченных коллекций, и я искал вариант передачи делегата сравнения, который просто случайным образом возвращает результат сравнения. Например:

int RandomComparison<T> (T x, T y)
{
    return this.random.Next (-1, 2);
}

Однако, поскольку я не знаю алгоритм сортировки, используемый под колпаком, я не знаю, может ли это привести к тому, что логика сортировки никогда не завершится. Хотя этот метод в целом ненадежен с точки зрения производительности, мне интересно, действительно ли он опасно непригоден?

Answer 1

Я предполагаю, что ваши подозрения верны.Вся предпосылка, на которой построен этот тип кода, заключается в том, что если A Вы можете связать случайное число с каждым элементом в коллекции, а затем выполнить стандартную сортировкуна это значение.

Answer 2

Найдите дефект: плохие сравнения, часть четвертая

Answer 3

List.Sort на самом деле задокументировано использование QuickSort (без дополнительных подробностей), но я проигнорирую это в пользу разговора о сортировке в целом ...

Я подозреваю, что для любой разумной сортировкиВ алгоритме этот компаратор приводит к завершению операции с вероятностью 1 в том смысле, что вероятность его продолжительного N шага стремится к 0, так как N стремится к бесконечности.На самом деле, я думаю, что во многих случаях существует жесткий верхний предел.

Причина в том, что вполне возможно (происходит с ненулевой вероятностью), что случайный компаратор может так и получиться, чтобы вернуть согласованные результаты для достаточного количества сравненийв ряду (O (n log n) из них, возможно, или O (n ^ 2) для сортировки вставки), что алгоритм «думает», что он закончен.Пока это в конце концов случится, я бы ожидал, что это прекратит сортировку.

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

В любом случае, это может занять очень много времени, достаточно долго, чтобы составить «опасность» для большинства практических целей.Например, пузырьковая сортировка будет просто продолжать перемешивать, пока не получит n отрицательных результатов подряд, чтобы завершить цикл, ничего не двигая.Это займет ожидаемое время 2^n или около того (не то, что List.Sort в частности может быть пузырьковой сортировкой, я использую его только для иллюстрации того, что может случиться для сортировки в целом).И в зависимости от деталей реализации, вы можете обнаружить, что вы получаете доступ за пределами, потому что «невозможное» происходит чаще, чем вы «заканчиваете».

Операция, безусловно, не Обязательно рандомизируйте коллекцию с равной вероятностью всех перестановок.Опять же, обратите внимание, что QuickSort выбирает стержень, а затем разделяет его.Учитывая этот случайный компаратор (и, опять же, не принимая фактических ошибок, таких как за пределами доступа), вероятность того, что первый выбранный стержень окажется в крайней правой части массива, равна 1 в 2 ^ (n-1) (поскольку все остальные элементы должны быть отсортированы слева от него, половина вероятности для каждого), тогда как при равномерно-случайно выбранной перестановке эта вероятность должна быть 1 на n.Первый выбранный стержень распределяется в массиве по кривой колокола, когда он «должен» быть равномерным.

Answer 4

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

Самый эффективный алгоритм перетасовки коллекции - это случай Фишера-Йейтса Он перетасует коллекцию в O (n), что лучше, чем любой алгоритм сортировки.

Answer 5

Как уже упоминалось, сортировка с использованием функции случайного сравнения не дает равномерного распределения перестановок и не должна использоваться.Но в любом случае ответить на вопрос ...

---

С теоретической точки зрения да вы можете зависать бесконечно в зависимости от выбора алгоритма сортировки.

ДляНапример, эта сортировка пузырей продолжается до тех пор, пока не будут произведены перестановки:

Из Википедии :

procedure bubbleSort( A : list of sortable items )
  do
    swapped = false
    for each i in 1 to length(A) - 1 inclusive do:
      if A[i-1] > A[i] then
        swap( A[i-1], A[i] )
        swapped = true
      end if
    end for
  while swapped
end procedure

Таким образом, вредоносная функция сравнения может сделать замену только двух значений ви бесконечно.

Однако все приличные алгоритмы, которые я могу придумать (быстрая сортировка, слияние, сортировка, вставка), используют только циклы for, поэтому их окончания не должны зависеть от правильности процедуры сортировки.Даже пузырьковая сортировка может быть сделана так, чтобы гарантировать завершение всего несколькими изменениями (посмотрите вики-ссылку для примеров)

Итак, с практической точки зрения, нет: Правильность сравненияфункция не должна влиять на поведение во время выполнения вида *

* по модулю таких вещей, как быстрая сортировка O (n ^ 2) в худшем случае ...

Answer 6

После того, как вы прошли процедуру сортировки функции, которая не дает последовательного порядка, нет гарантии, что произойдет.Можно было бы надеяться, что C # не делает ничего плохого, но из опыта я знаю, что C ++ имеет тревожную тенденцию сбрасывать ядро ​​в этой ситуации.