ब्लैक-बॉक्स मशीन

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\}$।