পাইথনে সন্নিবেশ সর্ট ব্যবহার করে একটি অ্যারে সাজানোর জন্য প্রয়োজনীয় শিফটের সংখ্যা খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি অ্যারে দেওয়া হয়েছে এবং এটিতে সন্নিবেশ বাছাই করতে বলা হয়েছে। সন্নিবেশ সাজানোর ক্ষেত্রে, অ্যারের প্রতিটি উপাদান অ্যারের সঠিক অবস্থানে স্থানান্তরিত হয়। আমাদের একটি অ্যারে সাজানোর জন্য প্রয়োজনীয় মোট শিফটের সংখ্যা খুঁজে বের করতে হবে। শিফটের মোট সংখ্যা হল একটি পূর্ণসংখ্যা এবং যদি অ্যারেটি ইতিমধ্যে সাজানো থাকে, তাহলে আমরা 0 ফেরত দিই।

সুতরাং, যদি ইনপুটটি হয় 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

শিফটের মোট সংখ্যা হল =0 + 0 + 2 + 3 + 3 =8।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

দৈর্ঘ্য :=ইনপুট_আরের আকার
temp_arr :=0s দিয়ে শুরু করা 1000001 আকারের একটি নতুন তালিকা
উত্তর :=0
input_arr-এ প্রতিটি আইটেমের জন্য করুন
- val :=আইটেম
- যখন val> 0, do
  - উত্তর :=ans + temp_arr[val]
  - val :=val - (val AND -val)
- val :=আইটেম
- যখন val <=1000000, do
  - temp_arr[val] :=temp_arr[val] + 1
  - val :=val + (val AND -val)
উত্তর :=দৈর্ঘ্য * (ফ্লোর মান (দৈর্ঘ্য - 1) / 2) - উত্তর
উত্তর ফেরত দিন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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]