Macchina Black-Box

Question

Supponiamo di avere una macchina misteriosa che restituisce la mediana $m$ di un dato set $S$ e impostare $S/\{m\}$ in tempo costante, dove $S/\{m\}$ denota la differenza di $S$ ed elemento $m$. Dimostra che possiamo ordinare qualsiasi elenco di file$n$elementi in tempo lineare utilizzando tale macchina. (è consentito spazio extra)

Ecco la mia idea, che funziona correttamente intuitivamente, ma non è stata in grado di dimostrarla matematicamente:

Crea un nuovo array con $n$ elementi e assegnare la mediana $m$ del set originale $S$al centro della matrice. In ogni iterazione, inseriamo una nuova mediana di$S/\{m\}$a destra oa sinistra dell'elemento utilizzato di recente: se era a sinistra, inserire una nuova mediana a sinistra di quell'elemento, e allo stesso modo per l'elemento più a destra. Tuttavia, non potevo pensare a come sarebbe possibile la dimostrazione matematica qui. Gradirei le tue prove complete per questo problema.

Nota: se il numero di elementi è pari, la mediana è definita come numero medio inferiore.

Answer 1

Questa risposta suppone che tu lo sappia $n$ in anticipo, ma può essere adattato al caso generale.

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

L'idea qui è che l'estrazione ripetuta della mediana produrrà gli elementi di $S$ ordinato in un ordine fisso che dipende solo da $n$. Possiamo determinare l'ordine eseguendo lo stesso processo sull'insieme di indici$\{1,\ldots,n\}$.