পাইথনে ইন্সারশন সর্ট দিয়ে অ্যারে সর্ট করার মোট শিফট সংখ্যা বের করার প্রোগ্রাম

একটি অ্যারে দেওয়া আছে। ইন্সারশন সর্টে প্রতিটি এলিমেন্ট তার সঠিক পজিশনে শিফট করা হয়। মোট কতবার শিফট হয়েছে সেটি বের করুন। অ্যালরেডি সোর্টেড হলে ০।

উদাহরণ

input_array = [4, 5, 3, 1, 2] → আউটপুট: 8

[4,5,3,1,2] = 0 shifts
[4,5,3,1,2] = 0 shifts
[3,4,5,1,2] = 2 shifts
[1,3,4,5,2] = 3 shifts
[1,2,3,4,5] = 3 shifts
Total = 8

এলগরিদম (Fenwick Tree / BIT)

1. temp_arr := [0]*1000001 (BIT)
2. ans := 0
3. প্রতিটি item ইন input_arr:
   • val := item; while val > 0: ans += temp_arr[val]; val -= val & -val
   • val := item; while val <= 1000000: temp_arr[val] += 1; val += val & -val
4. ans = n*(n-1)//2 - ans (টোটাল পেয়ার - ইতিমধ্যে সঠিক অর্ডারের পেয়ার)
5. 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] += 1
            val += val & -val
    ans = length * (length - 1) // 2 - ans
    return ans

print(solve([4, 5, 3, 1, 2]))  # আউটপুট: 8

ইনপুট / আউটপুট

[4, 5, 3, 1, 2]
8