Classificação usando uma caixa preta

Suponha que queremos classificar uma lista de números reais. Suponha que recebamos uma caixa preta que pode classificar números reais instantaneamente. Quanta vantagem podemos obter usando esta caixa preta?n $S$$n$$\sqrt n$

Por exemplo, podemos classificar os números com apenas chamadas para a caixa preta? O melhor algoritmo que eu encontrei usa chamadas para a caixa preta. Mas não consegui melhorá-lo ainda mais. Aqui está o meu algoritmo, que é semelhante ao merge-sort:$O(\sqrt n)$$n$

Primeiro, particione a lista em lista com tamanho aproximadamente . Em seguida, use chamadas para a caixa preta para classificar essas listas. Por fim, mescle as listas classificadas usando a caixa preta da seguinte maneira:$S$ s1,s2,. . . ,s$\sqrt n$$s_1, s_2, ..., s_{\sqrt n}$$\sqrt n$$\sqrt n$

Coloque os menores elementos das listas em uma nova lista e chame a caixa preta para classificá-la. O número em (primeiro e menor elemento de ) será o menor número em . Podemos colocá-lo em primeiro lugar da lista de saída. Assumindo que o elemento foi escolhido a partir de , substituímos com o segundo menor elemento da lista de classificação , e novamente executar a caixa preta sobre ele para calcular a segunda menor membro da . Continuamos até que todos os elementos sejam classificados. O número total de chamadas de caixa preta para esta parte seráL [ 1 ] L S s j L [ 1 ] s j S n - $L$$L[1]$$L$$S$
$s_j$$L[1]$$s_j$$S$
$n - \sqrt n$. Portanto, no geral, o número total de chamadas será .$n$

Por outro lado, parece que deveríamos obter um limite inferior usando o limite inferior nas comparações de números necessárias para classificar da seguinte maneira: Podemos implementar a caixa preta usando comparações. Se pudermos resolver o problema com chamadas para a caixa preta e mesclando em tempo linear, podemos classificar números reais com comparações que é impossível.o($\sqrt n \lg \sqrt n = \frac{1}{2} \sqrt n \lg n$no(nlgn$o(\sqrt n)$$n$$o(n \lg n)$

Acho que poderíamos provar que é um limite inferior para o número de chamadas para a caixa preta, pois muitas comparações usadas na caixa preta seriam compartilhadas e, portanto, são recontadas em nosso argumento.$\Omega(n)$

ATUALIZAÇÃO: Como as outras postagens sugerem, um também é possível.$\sqrt n \lg n$

É possível classificar com chamadas para a caixa preta e sem comparações.$O(\sqrt n\log n)$

Primeiro, considere o seguinte problema de particionamento balanceado: dados elementos (onde ), divida-os em dois grupos, o menor de tamanho pelo menos cerca de , portanto que todos os elementos no primeiro grupo são menores que todos os elementos no segundo grupo. Isso pode ser feito com chamadas para a caixa preta. (Descreverei isso mais tarde.) Em seguida, use quicksort com este algoritmo de particionamento:A [ 1 .. m ] $m$$A[1..m]$m/4O(m/$\sqrt n \le m \le n$$m/4$$O(m/\sqrt n)$

def qsort(A[1..m]):
   if m < sqrt(n): sort A with one call to the black box
   else:
     Partition A[1..m] into two groups as described above.
     Recursively qsort the first group.
     Recursively qsort the second group.

Supondo que cada etapa da partição receba chamadas para a caixa preta, o algoritmo acima, dado a entrada , fará chamadas para a caixa preta, porque a árvore de recursão possui profundidade e cada nível da árvore possui um total de chamadas para a caixa preta.A[1 ..n]O($O(m/\sqrt n)$$A[1..n]$O(logn)O(n/$O(\sqrt n\log n)$$O(\log n)$$O(n/\sqrt n) = O(\sqrt n)$

Execute a etapa de particionamento da seguinte maneira:

def partition(A[1..m]):  (where sqrt(n) <= m <= n)
   Divide A into m/sqrt(n) groups of size sqrt(n) each.
   Sort each group with one call to the black box per group.
   Sort the medians of the groups with one call to the black box.
   (Note the number of groups is less than sqrt(n), because m <= n.)
   Let X be the median of the medians.
   Partition all m elements around X, using the black box as follows:
      For each group G, let Y be its median:
        Call the black box once on (G - {Y}) union {X}.
        (This gives enough information to order all elts w.r.t. X.)

Acho que sua pergunta foi abordada no artigo de Beigel e Gill " Classificando n objetos usando o k-classificador " de 1990 e o resumo do artigo diz tudo:

Um classificador k é um dispositivo que classifica k objetos em tempo unitário. A complexidade de um algoritmo que usa um k-classificador é definida como o número de aplicações do k-classificador. Nesta medida, a complexidade da classificação de n objetos está entre e , até termos de primeira ordem em n e k.$\frac{n \log n}{k \log k}$$\frac{4n \log n}{k \log k}$

É possível classificar inconscientemente com chamadas para a caixa preta, cada uma aplicada a uma sub-matriz contígua da entrada original. O algoritmo nunca toca nos dados de entrada, exceto através de chamadas de caixa preta. Em particular, a mesma sequência de chamadas de caixa preta é apenas uma função de , não os dados de entrada reais (portanto, "inconscientes").$O(\sqrt{n}\log n)$$n$

Aqui está um esboço de um algoritmo mais simples, que usa uma caixa preta que classifica sub-matrizes de tamanho vez de apenas . O número total de chamadas para a caixa preta é aproximadamente . Para simplificar a notação, suponha que seja par e seja um número inteiro ímpar.$k$$\sqrt{n}$$2(n/k)^2$$k$$2n/k$

BlockBubbleSort(X[0..n-1], k):
   m = floor(n/k)
   for i = 1 to m
      for j = 0 to m-1
          BlackBoxSort(X[j*k .. (j+1)*k-1])
      for j = 0 to m-1
          BlackBoxSort(X[j*k + k/2 .. (j+1)*k + k/2 - 1])

Aqui é um diagrama do algoritmo para e . Os dados viajam da esquerda para a direita; cada caixa é um absorvedor de .$n=18$$k=4$$k$

Como a figura sugere, esperamos que esse algoritmo divida a matriz de entrada em pedaços de tamanho e, em seguida, aplique bolhasort aos pedaços, usando o absorvedor no lugar de uma operação de troca de comparação. A correção segue observando que a rede classifica corretamente qualquer matriz de 0s e 1s .$k/2$$k$

Como o comentário de @ VinayakPathak sugere, o limite pode ser reduzido substituindo o bubblesort por uma rede de classificação diferente. Por exemplo, a fusão par e ímpar do Batcher reduz o número de chamadas de caixa preta para e a rede de classificação da AKS reduz para . Este último algoritmo corresponde ao algoritmo não esquecido de Neal até (constantes !!) fatores constantes.O ( ( n / k ) log 2 ( n / k ) ) = O ( $O((n/k)^2)$O((n/k)log(n/k))=O($O((n/k)\log^2(n/k)) = O(\sqrt{n}\log^2 n)$$O((n/k)\log (n/k)) = O(\sqrt{n}\log n)$