पायथन में इंसर्शन सॉर्ट का उपयोग करके ऐरे को सॉर्ट करने के लिए आवश्यक शिफ्ट्स की संख्या ढूंढना

मान लीजिए हमें एक ऐरे दिया गया है और उस पर इंसर्शन सॉर्ट करने के लिए कहा गया है। इंसर्शन सॉर्ट में, ऐरे में प्रत्येक तत्व को ऐरे में अपनी सही पोजीशन पर शिफ्ट किया जाता है। हमें ऐरे को सॉर्ट करने के लिए आवश्यक कुल शिफ्ट्स की संख्या ढूंढनी है। कुल शिफ्ट्स की संख्या एक इंटीजर नंबर है और यदि ऐरे पहले से सॉर्टेड है, तो हम 0 लौटाते हैं।

उदाहरण के लिए, यदि इनपुट है input_array = [4, 5, 3, 1, 2], तो आउटपुट होगा 8।

[4, 5, 3, 1, 2] = 0 शिफ्ट्स
[4, 5, 3, 1, 2] = 0 शिफ्ट्स
[3, 4, 5, 1, 2] = 2 शिफ्ट्स
[1, 3, 4, 5, 2] = 3 शिफ्ट्स
[1, 2, 3, 4, 5] = 3 शिफ्ट्स

कुल शिफ्ट्स = 0 + 0 + 2 + 3 + 3 = 8।

समाधान दृष्टिकोण

फेनविक ट्री (बाइनरी इंडेक्स्ड ट्री) का उपयोग करके इंवर्जन काउंट की गणना करें, जो इंसर्शन सॉर्ट शिफ्ट्स के बराबर है।

length = len(input_arr)।
आकार 1,000,001 का temp_arr (BIT) 0 से आरंभ करें।
ans = 0।
प्रत्येक item के लिए input_arr में:
- val = item।
- जब val > 0: ans += temp_arr[val], val -= val & -val (क्वेरी)।
- val = item।
- जब val <= 1,000,000: temp_arr[val] += 1, val += val & -val (अपडेट)।
ans = length * (length - 1) // 2 - ans (कुल जोड़े - नॉन-इनवर्जन)।
ans लौटाएं।

पायथन कार्यान्वयन

def solve(input_arr):
    length = len(input_arr)
    temp_arr = [0] * 1000001
    ans = 0
    for item in input_arr:
        val = item
        while val > 0:
            ans += temp_arr[val]
            val -= val & -val
        val = item
        while val <= 1000000:
            temp_arr[val] = temp_arr[val] + 1
            val += val & -val
    ans = length * (length - 1) // 2 - ans
    return ans

print(solve([4, 5, 3, 1, 2]))

इनपुट

[4, 5, 3, 1, 2]