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

मान लीजिए, हमारे पास nums नामक एक सरणी है और हमें किसी भी क्रम में अंकों को क्रमबद्ध करने के लिए आवश्यक स्वैप की संख्या का पता लगाना है, या तो आरोही या अवरोही।

इसलिए, यदि इनपुट अंकों की तरह है =[2, 5, 6, 3, 4], तो आउटपुट 2 होगा क्योंकि शुरू में अंकों में [2, 5, 6, 3, 4] होता है। यदि हम संख्या 6 और 4 की अदला-बदली करते हैं, तो सरणी [2,5,4,3,6] होगी। फिर, यदि हम संख्या 5 और 3 की अदला-बदली करते हैं, तो सरणी [2,3,4,5,6] होगी। तो सरणी को आरोही क्रम में क्रमबद्ध करने के लिए 2 स्वैप की आवश्यकता होती है।

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

एक फ़ंक्शन को परिभाषित करें swap_count() । इसमें input_arr
- pos :=input_arr में प्रत्येक आइटम के लिए tuples (item_postion, item) वाली नई सूची
- input_arr में आइटम के अनुसार सूची स्थिति को क्रमबद्ध करें
- सीएनटी:=0
- 0 से लेकर input_arr के आकार के सूचकांक के लिए, करें
  - सच होने पर, करें
    - यदि pos[index, 0] इंडेक्स के समान है, तो
      - लूप से बाहर निकलें
    - अन्यथा,
      - cnt:=swap_count + 1
      - swap_index :=pos[index, 0]
      - (pos[index], pos[swap_index]) के मानों को स्वैप करें
- वापसी सीएनटी
मुख्य कार्य/विधि से, निम्न कार्य करें -
- कम से कम (swap_count(input_arr) , swap_count(input_arr रिवर्स ऑर्डर में))

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

def swap_count(input_arr):
   pos = sorted(list(enumerate(input_arr)), key=lambda x: x[1])
   cnt = 0

   for index in range(len(input_arr)):
      while True:
         if (pos[index][0] == index):
            break
         else:
            cnt += 1
            swap_index = pos[index][0]
            pos[index], pos[swap_index] = pos[swap_index], pos[index]

   return cnt

def solve(input_arr):
   return min(swap_count(input_arr), swap_count(input_arr[::-1]))

nums = [2, 5, 6, 3, 4]
print(solve(nums))

इनपुट

[2, 5, 6, 3, 4]