Алгоритмы сортировки, которые принимают случайный компаратор

Обычные алгоритмы сортировки обычно используют набор данных для сортировки и функцию сравнения, которая может сравнивать два отдельных элемента. Если компаратор представляет собой отношение порядка¹, то результатом алгоритма является отсортированный список / массив.

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

Из моего грубого умственного расчета кажется, что сортировка слиянием будет в порядке с этим и поддержит те же самые затраты времени выполнения и произведет справедливый случайный порядок. Я думаю, что что-то вроде быстрой сортировки, однако, выродится, возможно, не закончится и не будет справедливым.

Какие другие алгоритмы сортировки (кроме сортировки слиянием) будут работать, как описано со случайным компаратором?

1. Для справки, компаратор - это отношение порядка, если оно является надлежащей функцией (детерминированной) и удовлетворяет аксиомам отношения порядка:

   • он является детерминированным: compare(a,b)для конкретного aи bвсегда возвращает один и тот же результат.
   • это транзитивно: compare(a,b) and compare(b,c) implies compare( a,c )
   • это антисимметрично compare(a,b) and compare(b,a) implies a == b

(Предположим, что все входные элементы различны, поэтому рефлексивность не является проблемой.)

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

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

int Compare(object a, object b) { return Random.Next(-1,1); }

... где Random.Next () - это некоторый метод, который будет генерировать случайно сгенерированное целое число между указанной включающей нижней и верхней границей.

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

1. Сравнение между двумя уникальными элементами никогда не выполняется дважды в сортировке и / или
2. На каждой итерации сортировки определяется правильная позиция хотя бы одного элемента, поэтому этот элемент никогда не сравнивается снова.

Например, SelectionSort перебирает подсписок несортированных элементов, находит «наименьший» и / или «наибольший» элемент (сравнивая каждый из наибольших на данный момент), помещает его в правильную позицию и повторяет. В результате, даже с недетерминированным компаратором, в конце каждой итерации алгоритм найдет значение, которое он считает наименьшим или наибольшим, поменяет его на элемент в позиции, которую он пытается определить, и никогда не учитывает этот элемент снова, таким образом, он подчиняется условию 2. Тем не менее, A и B могут сравниваться несколько раз в течение этого процесса (в качестве самого крайнего примера рассмотрим несколько проходов SelectionSort для массива, отсортированного в обратном порядке), поэтому он нарушает условие 1 ,

MergeSort подчиняется условию 1, но не 2; поскольку подмассивы объединяются, элементы в одном и том же подмассиве (на левой или правой стороне) не сравниваются друг с другом, поскольку уже было определено, что элементы на этой стороне массива располагаются в порядке между собой; алгоритм сравнивает только наименее неотбираемый элемент каждого подмассива с другим, чтобы определить, какой из них меньше и должен идти следующим в объединенном списке. Это означает, что любые два уникальных объекта A и B будут сравниваться друг с другом не более одного раза, но «конечный» индекс любого данного элемента в полной коллекции не известен до тех пор, пока алгоритм не будет завершен.

InsertionSort подчиняется только условию 1, хотя его общая стратегия и сложность больше похожи на SelectionSort. Каждый несортированный элемент сравнивается с отсортированными элементами по возрастанию, пока не будет найден один элемент, который меньше проверяемого элемента. элемент вставляется в этот момент, а затем рассматривается следующий элемент. Результатом является то, что относительный порядок любых A и B определяется одним сравнением, и дальнейшие сравнения между этими A и B никогда не выполняются, но окончательное положение любого элемента не может быть известно, пока не будут рассмотрены все элементы.

QuickSort подчиняется обоимУсловия. На каждом уровне поворот выбирается и размещается таким образом, что «левая» сторона содержит элементы, меньшие, чем стержень, а «правая» сторона содержит элементы, превышающие стержень. Результатом этого уровня является QuickSort (слева) + pivot + QuickSort (справа), что в основном означает, что положение элемента pivot известно (на один индекс больше, чем длина левой стороны), pivot никогда не сравнивается с любым другим элементом. после того, как он был выбран в качестве точки поворота (его можно было сравнить с предыдущими элементами точки поворота, но эти элементы также известны и не включены ни в какие подрешетки), а любые А и В, которые заканчиваются на противоположных сторонах точки поворота, никогда не будут по сравнению. В большинстве реализаций чистой QuickSort базовый случай - это один элемент, в котором его текущий индекс является его конечным индексом, и дальнейшие сравнения не производятся.

Единственный сравнительный вид, о котором я могу подумать, что он не будет соответствовать ни одному из условий, - это неоптимизированная BubbleSort. Если сортировка не принимает, что наибольшие элементы X находятся на своем месте после выполнения проходов X, и / или использует проход «двойной проверки» для проверки сортировки списка, сортировка будет считаться «выполненной» только тогда, когда случайный компаратор возвратил -1 или 0 для каждых двух смежных элементов в списке во время прохода, и, таким образом, обмены не были выполнены (событие, которое, если оно действительно случайное, произойдет с вероятностью ; для сравнительно небольшого списка из 25 элементов это один шанс на 2000, в то время как для 100 элементов вероятность составляет 3,7 * 10 ^-18.$(2/3)^{N-1}$). По мере того, как максимальное абсолютное значение результата компаратора увеличивается, вероятность того, что какое-либо одно сравнение вернет отрицательное значение или ноль, уменьшается в сторону 0,5, что значительно снижает вероятность завершения алгоритма (вероятность 99 монет переворачивает все посадочные головки). Это то, к чему все сводится, 1 к 1,2 * 10 ³⁰ )

РЕДАКТИРОВАНИЕ ПОСЛЕДНЕГО ВРЕМЕНИ: Есть несколько «сортов», разработанных специально как примеры того, что не нужно делать, которые включают случайный компаратор; пожалуй, самым известным является BogoSort. Msgstr "Если список не в порядке, перетасуйте список и проверьте снова". Теоретически это в конечном итоге приведет к правильной перестановке значений, точно так же как «неоптимизированная BubbleSort» выше, но средний случай - факториальное время (N! / 2), и из-за проблемы дня рождения (после достаточно случайных перестановок вы с большей вероятностью встречаются повторяющиеся перестановки, чем уникальные) существует ненулевая вероятность того, что алгоритм никогда не завершится официально, алгоритм не ограничен по времени.

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

Я полагаю, что более интересный вопрос заключается в том, насколько хорошо будет работать такой алгоритм, если бы функция сравнения давала правильный ответ, скажем, в 90% случаев в среднем. Насколько хорошо это будет работать, я имею в виду ответить на вопрос: «Каково в среднем количество неуместных элементов при сортировке списка размера этим алгоритмом?»$n$

Редактировать: проблема более интересна, как я сначала подумал, поэтому вот еще один комментарий:

Предположим, что ваша функция справедлива , то есть с вероятностью и с вероятностью также . Напомним алгоритм сортировки вставок (функциональный стиль):$compare$$compare(x,y)=true$$1/2$$false$$1/2$

insert x [] = [x]
insert x y:ys = if x < y then x:y:ys
                else y:insert x ys

sort_aux l e = match l with
                 [] -> e
                 x:xs -> sort_aux xs (insert x ys)

sort l = sort_aux l []

Среднее время выполнения этого алгоритма тогда равно: где - длина а - среднее время выполнения в список длины , то есть, если мы считаем только приложения имеющими стоимость (если мы считаем и разрушения, формула аналогична).$\sum_{k=1}^{n} f(k)$$n$$l$$f(k)$$insert$$k$$:$

Теперь для как описано выше, это довольно мало: среднее количество шагов, выполняемых вставкой, определяется как:$compare$

Это дает среднее время работы для сортировки вставкой, что значительно лучше, чем заданное «приличной» функцией сравнения.O ( n 2$O(2n)$$O(n^2)$

Было бы интересно рассчитать среднее время выполнения для других алгоритмов, учитывая эту равномерную функцию сравнения.

Слияние с честным случайным компаратором не справедливо. У меня нет доказательств, но у меня есть ОЧЕНЬ сильные эмпирические доказательства. (Ярмарка означает равномерное распределение.)

module Main where

import Control.Monad
import Data.Map (Map)
import qualified Data.Map as Map
import System.Random (randomIO)

--------------------------------------------------------------------------------

main :: IO ()
main = do
  let xs = [0..9]
  xss <- replicateM 100000 (msortRand xs)
  print $ countFrequencies xss

msortRand :: [a] -> IO [a]
msortRand = msort (\_ _ -> randomIO)

countFrequencies :: (Ord a) => [[a]] -> [Map a Int]
countFrequencies [] = []
countFrequencies xss = foldr (\k m -> Map.insertWith (+) k 1 m) Map.empty ys : countFrequencies wss
  where
    ys = map head xss
    zss = map tail xss
    wss = if head zss == []
      then []
      else zss

--------------------------------------------------------------------------------

msort :: (Monad m) => (a -> a -> m Bool) -> [a] -> m [a]
msort (<) [] = return []
msort (<) [x] = return [x]
msort (<) xs = do
  ys' <- msort (<) ys
  zs' <- msort (<) zs
  merge (<) ys' zs'
  where
    (ys, zs) = split xs

merge :: (Monad m) => (a -> a -> m Bool) -> [a] -> [a] -> m [a]
merge (<) [] ys = return ys
merge (<) xs [] = return xs
merge (<) (x:xs) (y:ys) = do
  bool <- x < y
  if bool
    then liftM (x:) $ merge (<) xs (y:ys)
        else liftM (y:) $ merge (<) (x:xs) ys

split :: [a] -> ([a], [a])
split [] = ([], [])
split [x] = ([x], [])
split (x:y:zs) = (x:xs, y:ys)
  where
    (xs, ys) = split zs

Очень много связанных вопрос отвечает Всевозможные Перестановки (Functional Pearl) по Кристиансен, Даниленко и Dylus. Они запускают алгоритм сортировки в монаде списка , который по существу имитирует недетерминизм, возвращая все перестановки заданного входного списка. Интересным свойством является то, что каждая перестановка возвращается ровно один раз.

Цитирую из аннотации:

...

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

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