C++에서 배열을 정렬하는 데 필요한 최소 스왑 수

문제 설명

N개의 고유한 요소의 배열이 주어지면 배열을 정렬하는 데 필요한 최소 스왑 수를 찾으십시오.

예시

배열이 {4, 2, 1, 3}이면 2개의 스왑이 필요합니다.

• arr[0]을 arr[2]로 교체
• arr[2]을 arr[3}로 교체

알고리즘

1. Create a vector of pair in C++ with first element as array alues and second element as array indices.
2. Sort the vector of pair according to the first element of the pairs.
3. Traverse the vector and check if the index mapped with the value is correct or not, if not then keep swapping until the element is placed correctly and keep counting the number of swaps.

예시

#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(int *arr, int n) {
   vector<pair<int, int>> vec(n);
   for (int i = 0; i < n; ++i) {
      vec[i].first = arr[i];
      vec[i].second = i;
   }
   sort(vec.begin(), vec.end());
   int cnt = 0;
   for (int i = 0; i < n; ++i) {
      if (vec[i].second == i) {
         continue;
      }
      swap(vec[i].first,vec[vec[i].second].first);
      swap(vec[i].second,vec[vec[i].second].second);
      if (i != vec[i].second) {
         --i;
      }
         ++cnt;
   }
   return cnt;
}
int main() {
   int arr[] = {4, 2, 1, 3};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Minimum swaps = " << getMinSwaps(arr, n) <<
   endl;
   return 0;
}

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다.

출력

Minimum swaps = 2