Python에서 배열을 정렬하는 데 필요한 스왑 수를 찾는 프로그램

<시간/>

num이라는 배열이 있고 num을 오름차순 또는 내림차순으로 정렬하는 데 필요한 스왑 수를 찾아야 한다고 가정합니다.

따라서 입력이 nums =[2, 5, 6, 3, 4]와 같으면 초기에 nums에 [2, 5, 6, 3, 4]가 있기 때문에 출력은 2가 됩니다. 숫자 6과 4를 바꾸면 배열은 [2,5,4,3,6]이 됩니다. 그런 다음 숫자 5와 3을 바꾸면 배열은 [2,3,4,5,6]이 됩니다. 따라서 배열을 오름차순으로 정렬하려면 2번의 스왑이 필요합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

swap_count() 함수를 정의합니다. 이것은 input_arr
- pos :=input_arr의 각 항목에 대한 튜플(item_postion, item)을 포함하는 새 목록
- input_arr의 항목에 따라 목록 위치 정렬
- cnt :=0
- input_arr의 크기 범위 0에서 인덱스에 대해
  - 참일 때 수행
    - pos[index, 0]이 index와 같으면
      - 루프 종료
    - 그렇지 않으면
      - cnt :=swap_count + 1
      - swap_index :=pos[인덱스, 0]
      - (pos[index], pos[swap_index])의 값 교환
- 반환 cnt
메인 함수/메서드에서 다음을 수행합니다. -
- 반환 최소값(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]