इसे डुप्लिकेट के रूप में चिह्नित करने के लिए जल्दबाजी करने से पहले कृपया इसे पढ़ें! - यह वास्तविक संशोधन के बारे में नहीं है, यह जाँचने के बारे में है कि क्या किसी विशेष उलटा की गणना की गई है या नहीं।

तो लोकप्रिय सीएलआरएस 'एल्गोरिदम का परिचय पुस्तक में यह प्रश्न है जो आपको सरणी में व्युत्क्रमों की संख्या की गणना करने के लिए मर्ज सॉर्ट को संशोधित करने के लिए कहता है। लेखक उदारतापूर्वक इस समस्या का समाधान 2-4 यहां, जिनके स्क्रीनशॉट मैंने नीचे संलग्न किए हैं:

The MergeSort recursive function

The Merge function

मेरा प्रश्न: दूसरे स्क्रीनशॉट में, लेखक ने यह जांचने के लिए एक बूलियन counted = FALSE का उपयोग किया है कि क्या j के कुछ मान के लिए किसी विशेष R[j] से संबंधित व्युत्क्रम पहले ही गिने जा चुके हैं या नहीं। मैं इस वजह से काफी उलझन में हूं क्योंकि मुझे लगता है कि यह बेमानी है।

हम यहां व्युत्क्रमों की गणना करते हैं:

    if counted == FALSE and R[j] < L[i]   
        inversions = inversions + n1 - i + 1
        counted = TRUE 

So काउंटेड TRUE तभी बनता है जब R[j] < L[i], जो नीचे else का हिस्सा है:

    ...
    else
        A[k] = R[j]
        j = j + 1
        counted = FALSE
    

इसलिए जब भी हमारे पास R[j] < L[i] होता है, तो हम R[j] को A[k] में कॉपी कर लेते हैं और j के मान को 1 से बढ़ा देते हैं, जिससे यह सुनिश्चित हो जाता है कि हम कभी भी पिछले R[j] का सामना नहीं करेंगे। पाश में। मेरी राय में यह counted बूलियन को निरर्थक बना देता है।

या इसमें कुछ और है? क्या कोई विशेष उदाहरण है जो टूट जाता है यदि हम counted बूलियन को हटा दें:

    // my suggestion
    ...
    for k = p to r
        if R[j] < L[i]
            inversions = inversions + n1 - i + 1
        if L[i] <= R[j]
            A[k] = L[i]
            i = i + 1
        else A[k] = R[j]
            j = j + 1
2
Utkarsh Gupta 22 अगस्त 2020, 15:18

1 उत्तर

सबसे बढ़िया उत्तर

मेरे विचार से तुम सही हो। समाधान लेखक एक अनुभवी एल्गोरिथम है, लेकिन हल करने के लिए अभ्यास की एक पूरी किताब के साथ, यह अपरिहार्य है कि कुछ उत्तर सही नहीं होंगे।

आप लेखकों को क्यों नहीं लिखते?

1
David Eisenstat 22 अगस्त 2020, 12:37