Machine à boîte noire

Question

Supposons que nous ayons une machine mystérieuse qui renvoie la médiane $m$ d'un ensemble donné $S$ Et mettre $S/\{m\}$ en temps constant, où $S/\{m\}$ dénote la différence de $S$ et élément $m$. Prouvez que nous pouvons trier n'importe quelle liste de$n$éléments en temps linéaire en utilisant une telle machine. (un espace supplémentaire est autorisé)

Voici mon idée, qui fonctionne intuitivement correctement, mais n'a pas pu le prouver mathématiquement:

Créez un nouveau tableau avec $n$ éléments et attribuer la médiane $m$ de l'ensemble d'origine $S$au milieu du tableau. À chaque itération, nous mettons une nouvelle médiane de$S/\{m\}$à droite ou à gauche de l'élément récemment utilisé: s'il était à gauche, mettez une nouvelle médiane à gauche de cet élément, et de même pour l'élément le plus à droite. Cependant, je ne pouvais pas penser à la façon dont une preuve mathématique serait possible ici. Je serais heureux de recevoir vos preuves complètes de ce problème.

Remarque: si le nombre d'éléments est pair, la médiane est définie comme un nombre moyen plus petit.

Answer 1

Cette réponse suppose que vous savez $n$ à l'avance, mais peut être adapté au cas général.

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'idée ici est que l'extraction répétée de la médiane produira les éléments de $S$ triés dans un ordre fixe qui ne dépend que de $n$. On peut déterminer l'ordre en exécutant le même processus sur l'ensemble des indices$\{1,\ldots,n\}$.