Mesin Kotak Hitam

Question

Misalkan kita memiliki mesin misterius yang mengembalikan median $m$ dari set yang diberikan $S$ dan set $S/\{m\}$ dalam waktu yang konstan, di mana $S/\{m\}$ menunjukkan perbedaan $S$ dan elemen $m$. Buktikan bahwa kami dapat menyortir daftar apa pun$n$elemen dalam waktu linier menggunakan mesin tersebut. (ruang ekstra diperbolehkan)

Inilah ide saya, yang bekerja secara intuitif benar, tetapi tidak dapat membuktikannya secara matematis:

Buat array baru dengan $n$ elemen dan menetapkan median $m$ dari set asli $S$ke tengah larik. Di setiap iterasi, kami menempatkan median baru$S/\{m\}$ke kanan atau kiri elemen yang baru saja digunakan: jika berada di sebelah kiri, letakkan median baru di sebelah kiri elemen tersebut, dan demikian juga untuk elemen paling kanan. Namun, saya tidak bisa memikirkan bagaimana pembuktian matematis mungkin terjadi di sini. Kami akan menyambut baik bukti komprehensif Anda untuk masalah ini.

Catatan: Jika jumlah elemen genap, median didefinisikan sebagai angka tengah yang lebih kecil.

Answer 1

Jawaban ini mengandaikan bahwa Anda tahu $n$ sebelumnya, tetapi dapat disesuaikan dengan kasus umum.

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

Idenya di sini adalah bahwa mengekstrak median berulang kali akan mengeluarkan elemen $S$ diurutkan dalam beberapa urutan tetap yang hanya bergantung pada $n$. Kami dapat menentukan pesanan dengan menjalankan proses yang sama pada kumpulan indeks$\{1,\ldots,n\}$.