Máy hộp đen

Question

Giả sử chúng ta có máy bí ẩn trả về giá trị trung bình $m$ của tập hợp nhất định $S$ và thiết lập $S/\{m\}$ trong thời gian không đổi, ở đâu $S/\{m\}$ biểu thị sự khác biệt của $S$ và phần tử $m$. Chứng minh rằng chúng tôi có thể sắp xếp bất kỳ danh sách$n$các yếu tố trong thời gian tuyến tính bằng cách sử dụng máy như vậy. (cho phép thêm không gian)

Đây là ý tưởng của tôi, hoạt động chính xác về mặt trực quan, nhưng không thể chứng minh nó bằng toán học:

Tạo một mảng mới với $n$ các phần tử và chỉ định trung vị $m$ của bộ ban đầu $S$vào giữa mảng. Trong mỗi lần lặp lại, chúng tôi đặt giá trị trung bình mới là$S/\{m\}$vào bên phải hoặc bên trái của phần tử được sử dụng gần đây: nếu nó ở bên trái, hãy đặt trung vị mới ở bên trái phần tử đó và tương tự cho phần tử ngoài cùng bên phải. Tuy nhiên, tôi không thể nghĩ về cách có thể chứng minh toán học ở đây. Rất hoan nghênh các bằng chứng toàn diện của bạn cho vấn đề này.

Lưu ý: Nếu số phần tử là chẵn, số trung vị được định nghĩa là số ở giữa nhỏ hơn.

Answer 1

Câu trả lời này giả sử rằng bạn biết $n$ trước, nhưng có thể được điều chỉnh cho phù hợp với trường hợp chung.

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

Ý tưởng ở đây là liên tục trích xuất trung vị sẽ xuất ra các phần tử của $S$ được sắp xếp theo một số thứ tự cố định chỉ phụ thuộc vào $n$. Chúng tôi có thể xác định thứ tự bằng cách chạy cùng một quy trình trên tập hợp các chỉ số$\{1,\ldots,n\}$.