Algoritmos de classificação que aceitam um comparador aleatório

Os algoritmos de classificação genérica geralmente levam um conjunto de dados para classificar e uma função comparadora que pode comparar dois elementos individuais. Se o comparador for uma relação de ordem¹, a saída do algoritmo será uma lista / matriz classificada.

Gostaria de saber, porém, quais algoritmos de classificação realmente funcionariam com um comparador que não é uma relação de ordem (em particular uma que retorna um resultado aleatório em cada comparação). Por "trabalho", quero dizer aqui que eles continuam retornando uma permutação de suas entradas e rodando em sua complexidade de tempo tipicamente citada (em vez de degradar sempre o pior cenário possível, ou entrar em um loop infinito ou elementos ausentes). A ordenação dos resultados seria indefinida. Melhor ainda, a ordenação resultante seria uma distribuição uniforme quando o comparador for um lançamento de moeda.

Do meu cálculo mental, parece que uma classificação de mesclagem seria boa com isso e manteria o mesmo custo de tempo de execução e produziria uma ordenação aleatória justa. Eu acho que algo como uma classificação rápida, no entanto, degeneraria, possivelmente não terminaria e não seria justo.

Quais outros algoritmos de classificação (exceto a classificação por mesclagem) funcionariam conforme descrito com um comparador aleatório?

1. Para referência, um comparador é uma relação de ordem, se for uma função adequada (determinística) e satisfizer os axiomas de uma relação de ordem:

   • é determinístico: compare(a,b)para um determinado ae bsempre retorna o mesmo resultado.
   • é transitivo: compare(a,b) and compare(b,c) implies compare( a,c )
   • é anti-simétrico compare(a,b) and compare(b,a) implies a == b

(Suponha que todos os elementos de entrada sejam distintos, portanto a reflexividade não é um problema.)

Um comparador aleatório viola todas essas regras. No entanto, existem comparadores que não são relações de ordem e ainda não são aleatórios (por exemplo, eles podem violar talvez apenas uma regra e apenas para elementos específicos do conjunto).

Então, basicamente, você deseja saber se existe algum algoritmo de classificação que não seria degradado do seu caso médio se receber uma função de comparação semelhante a:

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

... em que Random.Next () é um método que produzirá um número inteiro gerado aleatoriamente entre um limite inferior e superior inclusivo especificado.

A resposta é, na verdade, que os algoritmos de classificação mais básicos serão executados de acordo com o caso médio, porque eles obedecem a pelo menos uma das duas condições a seguir:

1. Uma comparação entre dois elementos únicos nunca é feita duas vezes na classificação e / ou
2. Em cada iteração da classificação, a posição correta de pelo menos um elemento é determinada e, para que esse elemento nunca seja comparado novamente.

Por exemplo, SelectionSort percorre a sub-lista de elementos não classificados, encontra o elemento "mínimo" e / ou "maior" (comparando cada um com o maior até agora), coloca-o em sua posição correta e repete. Como resultado, mesmo com um comparador não determinístico, no final de cada iteração, o algoritmo encontrou um valor que considera menor ou maior, troca-o pelo elemento na posição que está tentando determinar e nunca considera esse elemento novamente, portanto, ele obedece à condição 2. No entanto, um A e B podem ser comparados várias vezes durante esse processo (como o exemplo mais extremo, considere várias passagens de SelectionSort em uma matriz classificada em ordem inversa), por isso viola a condição 1 .

MergeSort obedece à condição 1, mas não 2; À medida que as sub-matrizes são mescladas, os elementos na mesma sub-matriz (no lado esquerdo ou direito) não são comparados entre si porque já foi determinado que os elementos desse lado da matriz estão em ordem entre si; o algoritmo compara apenas o elemento menos imerso de cada sub-matriz com o outro para determinar qual é menor e deve seguir em seguida na lista mesclada. Isso significa que quaisquer dois objetos exclusivos A e B serão comparados entre si no máximo uma vez, mas o índice "final" de qualquer elemento na coleção completa não será conhecido até que o algoritmo esteja completo.

O InsertionSort obedece apenas à Condição 1, apesar de sua estratégia e complexidade gerais parecerem mais com SelectionSort. Cada elemento não classificado é comparado aos elementos classificados, o maior primeiro, até encontrar um que seja menor que o elemento sob inspeção. o elemento é inserido nesse ponto e, em seguida, o próximo elemento é considerado. O resultado é que a ordem relativa de qualquer A e B é determinada por uma comparação e nunca são realizadas comparações adicionais entre A e B, mas a posição final de qualquer elemento não pode ser conhecida até que todos os elementos sejam considerados.

O QuickSort obedece a ambosCondições. Em cada nível, um pivô é escolhido e organizado de forma que o lado "esquerdo" contenha elementos menos que o pivô e o lado "direito" contenha elementos maiores que o pivô. O resultado desse nível é QuickSort (esquerda) + pivô + QuickSort (direita), o que basicamente significa que a posição do elemento pivô é conhecida (um índice maior que o comprimento do lado esquerdo); o pivô nunca é comparado a qualquer outro elemento depois de ter sido escolhido como um pivô (ele pode ter sido comparado com elementos de pivô anteriores, mas esses elementos também são conhecidos e não estão incluídos em nenhum sub-arranjo) E os A e B que terminam em lados opostos do pivô nunca são comparado. Na maioria das implementações do QuickSort puro, o caso base é um elemento; nesse momento, o índice atual é o índice final e nenhuma comparação adicional é feita.

$(2/3)^{N-1}$) À medida que o valor absoluto máximo do resultado do comparador aumenta, a probabilidade de qualquer comparação retornar negativo ou zero diminui para 0,5, tornando a chance de terminar o algoritmo muito menos provável (a chance de 99 moedas vira todas as cabeças de aterrissagem , que é basicamente o que isso se resume, é 1 em 1,2 * 10 ³⁰ )

EDITAR MUITO TEMPO DEPOIS: Existem alguns "tipos" projetados especificamente como exemplos do que não fazer que incorporam um comparador aleatório; talvez o mais famoso seja o BogoSort. "Dada uma lista, se a lista não estiver em ordem, embaralhe a lista e verifique novamente". Teoricamente, acabará atingindo a permutação correta de valores, assim como o "BubbleSort não otimizado" acima, mas o caso médio é de fatorial (N! / 2) e devido ao problema de aniversário (após permutações aleatórias suficientes maior probabilidade de encontrar permutações duplicadas do que as únicas) existe uma possibilidade diferente de zero de o algoritmo nunca concluir para oficialmente o algoritmo não ter limite de tempo.

$O(n^2)$

$n$

Edit: O problema é mais interessante como eu pensava, então aqui está um comentário adicional:

$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(2n)$$O(n^2)$

Seria divertido calcular os tempos médios de execução para os outros algoritmos, dada essa função de comparação uniforme.

A fusão com um comparador aleatório justo não é justa. Não tenho prova, mas tenho evidências empíricas MUITO fortes. (Justo significa distribuído uniformemente.)

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

Uma pergunta muito relacionada é respondida em Todos os tipos de permutações (pérola funcional) por Christiansen, Danilenko e Dylus. Eles executam um algoritmo de classificação na mônada da lista , que simula essencialmente o não determinismo, retornando todas as permutações de uma determinada lista de entrada. A propriedade interessante é que cada permutação é retornada exatamente uma vez.

Citando o resumo:

...

Neste artigo, examinamos a combinação de não determinismo e classificação de uma maneira diferente: dada uma função de classificação, aplicamos a um predicado não determinístico para obter uma função que enumera permutações da lista de entrada. Chegamos ao fundo das propriedades necessárias dos algoritmos e predicados de classificação em jogo, bem como discutimos variações do não determinismo modelado.

Além disso, formulamos e provamos um teorema declarando que, independentemente da função de classificação que usamos, a função de permutação correspondente enumera todas as permutações da lista de entrada. Usamos teoremas livres, derivados apenas do tipo de uma função, para provar a afirmação.