पायथन में सम्मिलन प्रकार का उपयोग करके एक सरणी को सॉर्ट करने के लिए आवश्यक पारियों की संख्या का पता लगाने के लिए कार्यक्रम

मान लीजिए हमें एक ऐरे दिया गया है और उस पर इंसर्शन सॉर्ट करने के लिए कहा गया है। सम्मिलन क्रम में, सरणी में प्रत्येक तत्व को सरणी में उसकी सही स्थिति में स्थानांतरित कर दिया जाता है। हमें किसी सरणी को सॉर्ट करने के लिए आवश्यक कुल पारियों की संख्या का पता लगाना है। पारियों की कुल संख्या एक पूर्णांक संख्या है और यदि सरणी पहले से ही क्रमबद्ध है, तो हम 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.

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

लंबाई:=input_arr का आकार
temp_arr :=आकार 1000001 की एक नई सूची 0s के साथ आरंभ की गई
उत्तर:=0
इनपुट_एआर में प्रत्येक आइटम के लिए, करें
- वैल:=आइटम
- जबकि वैल> 0, करें
  - उत्तर:=उत्तर + temp_arr[val]
  - वैल:=वैल - (वैल एंड -वैल)
- वैल:=आइटम
- जबकि वैल <=1000000, करें
  - temp_arr[val] :=temp_arr[val] + 1
  - वैल:=वैल + (वैल एंड -वैल)
उत्तर:=लंबाई * (फर्श का मान (लंबाई -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]