Black-Box-Maschine

Question

Angenommen, wir haben eine mysteriöse Maschine, die den Median zurückgibt $m$ des gegebenen Satzes $S$ und setzen $S/\{m\}$ in konstanter Zeit, wo $S/\{m\}$ bezeichnet den Unterschied von $S$ und Element $m$. Beweisen Sie, dass wir jede Liste von sortieren können$n$Elemente in linearer Zeit mit einer solchen Maschine. (zusätzlicher Platz ist erlaubt)

Hier ist meine Idee, die intuitiv korrekt funktioniert, sie aber mathematisch nicht beweisen konnte:

Erstellen Sie ein neues Array mit $n$ Elemente und Median zuweisen $m$ des ursprünglichen Satzes $S$in die Mitte des Arrays. In jeder Iteration setzen wir einen neuen Median von$S/\{m\}$rechts oder links vom zuletzt verwendeten Element: Wenn es links war, setzen Sie links von diesem Element einen neuen Median und in ähnlicher Weise für das Element ganz rechts. Ich konnte mir jedoch nicht vorstellen, wie ein mathematischer Beweis hier möglich wäre. Würde mich über Ihre umfassenden Beweise für dieses Problem freuen.

Hinweis: Wenn die Anzahl der Elemente gerade ist, wird der Median als kleinere mittlere Zahl definiert.

Answer 1

Diese Antwort setzt voraus, dass Sie es wissen $n$ im Voraus, kann aber an den allgemeinen Fall angepasst werden.

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

Die Idee hier ist, dass durch wiederholtes Extrahieren des Medians die Elemente von ausgegeben werden $S$ sortiert in einer festen Reihenfolge, die nur von abhängt $n$. Wir können die Reihenfolge bestimmen, indem wir denselben Prozess für den Satz von Indizes ausführen$\{1,\ldots,n\}$.