เครื่อง Black-Box

Question

สมมติว่าเรามีเครื่องจักรลึกลับที่ส่งกลับค่ามัธยฐาน $m$ ของชุดที่กำหนด $S$ และตั้งค่า $S/\{m\}$ ในเวลาคงที่โดยที่ $S/\{m\}$ แสดงถึงความแตกต่างของ $S$ และองค์ประกอบ $m$. พิสูจน์ว่าเราสามารถจัดเรียงรายการใดก็ได้$n$องค์ประกอบในเวลาเชิงเส้นโดยใช้เครื่องดังกล่าว (อนุญาตให้มีพื้นที่เพิ่มเติม)

นี่คือความคิดของฉันซึ่งใช้งานได้ถูกต้องตามสัญชาตญาณ แต่ไม่สามารถพิสูจน์ได้ในเชิงคณิตศาสตร์:

สร้างอาร์เรย์ใหม่ด้วย $n$ องค์ประกอบและกำหนดค่ามัธยฐาน $m$ ของชุดเดิม $S$ตรงกลางอาร์เรย์ ในการวนซ้ำแต่ละครั้งเราใส่ค่ามัธยฐานใหม่ของ$S/\{m\}$ไปทางขวาหรือซ้ายขององค์ประกอบที่เพิ่งใช้: ถ้าอยู่ทางซ้ายให้ใส่ค่ามัธยฐานใหม่ทางด้านซ้ายขององค์ประกอบนั้นและในทำนองเดียวกันสำหรับองค์ประกอบด้านขวาสุด อย่างไรก็ตามฉันไม่สามารถคิดได้ว่าจะพิสูจน์ทางคณิตศาสตร์ได้อย่างไรที่นี่ ยินดีรับข้อพิสูจน์ที่ครอบคลุมสำหรับปัญหานี้

หมายเหตุ: หากจำนวนองค์ประกอบเท่ากันค่ามัธยฐานจะถูกกำหนดเป็นจำนวนกลางที่น้อยกว่า

Answer 1

คำตอบนี้สมมติว่าคุณรู้ $n$ ล่วงหน้า แต่สามารถปรับให้เข้ากับกรณีทั่วไปได้

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

แนวคิดในที่นี้คือการแยกค่ามัธยฐานซ้ำ ๆ จะส่งออกองค์ประกอบของ $S$ จัดเรียงตามลำดับคงที่ซึ่งขึ้นอยู่กับ $n$. เราสามารถกำหนดลำดับได้โดยใช้กระบวนการเดียวกันกับชุดดัชนี$\{1,\ldots,n\}$.