न्यूनतम संख्या। 3 संख्या

Question

के मध्यस्थ को खोजने के लिए तुलना की तुलना में मैं क्विकॉर्ट को कार्यान्वित कर रहा था और मैं पिवट को औसत या तीन नंबरों के रूप में सेट करना चाहता था। तीन संख्याएं पहला तत्व, मध्य तत्व, और अंतिम तत्व हैं।

क्या मैं संभवतः कम संख्या में औसत प्राप्त कर सकता हूं। तुलना की?

median(int a[], int p, int r) 
{ 
    int m = (p+r)/2; 
    if(a[p] < a[m]) 
    { 
     if(a[p] >= a[r]) 
      return a[p]; 
     else if(a[m] < a[r]) 
      return a[m]; 
    } 
    else 
    { 
     if(a[p] < a[r]) 
      return a[p]; 
     else if(a[m] >= a[r]) 
      return a[m]; 
    } 
    return a[r]; 
} 

Answer 1

आप एक में कर सकते हैं नहीं है, और आप केवल दो या तीन का उपयोग कर रहे हैं, इसलिए मैं कहेंगे आप पहले से ही तुलना की न्यूनतम संख्या मिल गया है।

Answer 2

केवल मध्यस्थ की गणना करने की बजाय, आप उन्हें जगह में भी डाल सकते हैं। फिर आप हर समय केवल 3 तुलनाओं से दूर हो सकते हैं, और आपको अपने पिवट को जगह के करीब मिल गया है।

T median(T a[], int low, int high) 
{ 
    int middle = (low + high)/2; 
    if(a[ middle ].compareTo(a[ low ]) < 0) 
     swap(a, low, middle); 
    if(a[ high ].compareTo(a[ low ]) < 0) 
     swap(a, low, high); 
    if(a[ high ].compareTo(a[ middle ]) < 0) 
     swap(a, middle, high); 

    return a[middle]; 
} 

Answer 3

आप संकलक intrinsics साथ अपने हाथों को एक छोटे से गंदा होने में संकोच नहीं कर रहे हैं आप यह वास्तव में 0 शाखाओं के साथ कर सकते हैं।

वही सवाल से पहले पर चर्चा की गई:
Fastest way of finding the middle value of a triple?

हालांकि, मैं जोड़ने के लिए है कि quicksort की भोली कार्यान्वयन के संदर्भ में, तत्वों का एक बहुत कुछ के साथ, शाखाओं की मात्रा को कम जब मंझला ढूंढने में समस्या है इतना महत्वपूर्ण नहीं है क्योंकि शाखा भविष्यवाणी किसी भी तरह से चकित होगी जब आप पिवट के चारों ओर तत्वों को फेंकना शुरू कर देंगे। अधिक परिष्कृत कार्यान्वयन (जो विभाजन संचालन पर शाखा नहीं है, और डब्ल्यूएडब्ल्यू खतरों से बचें) इससे बहुत फायदा होगा।

Answer 4

वास्तव में 6 संभावित क्रमिक (कम, औसत, उच्च) के सावधानीपूर्वक विश्लेषण का उपयोग करके तीन से मध्य तत्व को अलग करने का एक चालाक तरीका है। पायथन में:

def med(a, start, mid, last): 
    # put the median of a[start], a[mid], a[last] in the a[start] position 
    SM = a[start] < a[mid] 
    SL = a[start] < a[last] 
    if SM != SL: 
     return 
    ML = a[mid] < a[last] 
    m = mid if SM == ML else last 
    a[start], a[m] = a[m], a[start] 

आधा समय आपके पास दो तुलना है अन्यथा आपके पास 3 (औसत 2.5) है। और आवश्यकता होने पर आप केवल मध्य तत्व को स्वैप करें (समय के 2/3)।

पूर्ण अजगर पर इस का उपयोग करते हुए quicksort:

https://github.com/mckoss/labs/blob/master/qs.py

Answer 5

आप सभी क्रमपरिवर्तन ऊपर लिख सकते हैं:

1 0 2 
    1 2 0 
    0 1 2 
    2 1 0 
    0 2 1 
    2 0 1 

फिर हम 1 की स्थिति का पता लगाने के लिए चाहते हैं। हम इसे दो तुलनाओं के साथ कर सकते हैं, अगर हमारी पहली तुलना बराबर पदों के समूह को विभाजित कर सकती है, जैसे कि पहली दो पंक्तियां।

समस्या यह प्रतीत होती है कि हमारे पास उपलब्ध किसी भी तुलना पर पहली दो पंक्तियां अलग हैं: a<b, a<c, b<c। इसलिए हमें क्रमपरिवर्तन की पूरी तरह से पहचान करनी है, जिसके लिए सबसे खराब मामले में 3 तुलना की आवश्यकता है।

Answer 6

यदि चिंता केवल तुलना है, तो इसका उपयोग किया जाना चाहिए।

int getMedian(int a, int b , int c) { 
    int x = a-b; 
    int y = b-c; 
    int z = a-c; 
    if(x*y > 0) return b; 
    if(x*z > 0) return c; 
    return a; 
} 

Answer 7

int32_t FindMedian(const int n1, const int n2, const int n3) { 
    auto _min = min(n1, min(n2, n3)); 
    auto _max = max(n1, max(n2, n3)); 
    return (n1 + n2 + n3) - _min - _max; 
} 

Answer 8

मुझे पता है कि यह एक पुराने धागा है, लेकिन मैं एक माइक्रो बहुत कम रैम है और एक घंटा भी नहीं है/गुणा इकाई (:)) w पर वास्तव में इस समस्या को हल करने के लिए किया था।अंत में मैंने निम्नलिखित कार्यों को अच्छी तरह से पाया:

static char medianIndex[] = { 1, 1, 2, 0, 0, 2, 1, 1 }; 

signed short getMedian(const signed short num[]) 
{ 
    return num[medianIndex[(num[0] > num[1]) << 2 | (num[1] > num[2]) << 1 | (num[0] > num[2])]]; 
}