Máquina Black-Box

Question

Suponha que temos uma máquina misteriosa que retorna mediana $m$ de determinado conjunto $S$ E definir $S/\{m\}$ em tempo constante, onde $S/\{m\}$ denota a diferença de $S$ e elemento $m$. Prove que podemos classificar qualquer lista de$n$elementos em tempo linear usando tal máquina. (espaço extra é permitido)

Aqui está minha ideia, que funciona intuitivamente correta, mas não conseguiu prová-la matematicamente:

Crie uma nova matriz com $n$ elementos e atribuir mediana $m$ do conjunto original $S$para o meio da matriz. Em cada iteração, colocamos uma nova mediana de$S/\{m\}$à direita ou à esquerda do elemento usado recentemente: se estiver à esquerda, coloque uma nova mediana à esquerda desse elemento e da mesma forma para o elemento mais à direita. No entanto, eu não conseguia pensar em como a prova matemática seria possível aqui. Agradeceria suas provas abrangentes para este problema.

Nota: Se o número de elementos for par, a mediana é definida como um número médio menor.

Answer 1

Esta resposta supõe que você sabe $n$ com antecedência, mas pode ser adaptado ao caso geral.

Sort(S)
  n ← length(S)
  T ← {1,...,n}
  A ← new array of length n
  repeat n times:
    S, m_S = extract_median(S)
    T, m_T = extract_median(T)
    A[m_T] = m_S
  end repeat
  return A

A ideia aqui é que extrair repetidamente a mediana produzirá os elementos de $S$ classificados em alguma ordem fixa que depende apenas de $n$. Podemos determinar a ordem executando o mesmo processo no conjunto de índices$\{1,\ldots,n\}$.