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

https://cs.stackexchange.com/questions/2336

16-10-2019
|

Вопрос

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

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

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

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

Для справки, компаратор является отношением порядка, если он является правильной функцией (детерминированной) и удовлетворяет аксиомам отношения порядка:
- она детерминирована: 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() - это некоторый метод, который выдаст случайно сгенерированное целое число между указанной включающей нижней и верхней границами.

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

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

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

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

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

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

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

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

Другие советы

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

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

РЕДАКТИРОВАТЬ: Проблема более интересна, как я впервые подумал, так что вот еще один комментарий:

Предположим, что ваша функция $ сравнить $ справедливый, это $ 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) $ - это среднее время выполнения $ вставьте $ в список длины $ k $, то есть, если мы считаем только приложения $: $ как стоимость (если мы также считаем разрушения, формула аналогична).

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

$$ sum_ {i = 1}^{k} i 2^{-i} leq sum_ {i = 1}^{ infty} i 2^{-i} = 2 $$

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

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

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

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

Ответ очень связан с Все виды перестановки (функциональная жемчужина) Кристиансен, Даниленко и Дилус. Они управляют алгоритмом сортировки в Список монады, который по существу имитирует нетерминизм, возвращая все перестановки данного списка ввода. Интересная собственность заключается в том, что каждая перестановка возвращается ровно один раз.

Цитата из реферата:

...

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с cs.stackexchange