C++로 배열 정렬에 필요한 최소 스왑(교환) 횟수 구하기

문제 개요

서로 다른 N개의 원소로 구성된 배열이 주어졌을 때, 이 배열을 오름차순으로 정렬하기 위해 필요한 최소 스왑(교환) 횟수를 구하는 것이 이 글의 목표입니다.

예시

배열이 {4, 2, 1, 3}이라면 단 2번의 스왑만으로 정렬을 완료할 수 있습니다.

• arr[0]과 arr[2]를 교환 → {1, 2, 4, 3}
• arr[2]과 arr[3]을 교환 → {1, 2, 3, 4}

즉, 무작정 인접한 두 원소를 반복해서 바꾸는 것보다, 각 원소가 최종적으로 위치해야 할 자리를 파악한 뒤 한 번에 올바른 위치로 옮기는 전략이 훨씬 효율적입니다.

알고리즘 접근 방법

1. C++의 pair 벡터를 생성하고, 첫 번째 요소에는 배열의 값, 두 번째 요소에는 해당 값의 원래 인덱스를 저장합니다.
2. pair의 첫 번째 요소(값)를 기준으로 벡터를 오름차순 정렬합니다.
3. 벡터를 순회하면서 각 값에 매핑된 인덱스가 현재 위치와 일치하는지 확인합니다. 일치하지 않으면 해당 요소가 제자리에 놓일 때까지 계속 교환(swap)하고, 그때마다 스왑 횟수를 카운트합니다.

이 방식은 사이클(cycle) 단위로 원소들의 위치를 추적하기 때문에, 불필요한 중간 교환 없이 이론상 최소한의 스왑만 수행할 수 있습니다.

C++ 구현 예제

#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

복잡도 분석

pair 벡터를 정렬하는 데 O(N log N)의 시간이 소요되며, 이후 순회 및 교환 과정은 각 원소가 최대 한 번씩 제자리에 배치되므로 O(N)입니다. 따라서 전체 시간 복잡도는 O(N log N)입니다. 추가로 pair 벡터를 저장해야 하므로 공간 복잡도는 O(N)입니다.