Số lần hoán đổi tối thiểu để sắp xếp mảng trong C++

Đề bài

Cho mảng N phần tử khác nhau, tìm số lần hoán đổi tối thiểu để sắp xếp mảng.

Ví dụ

Nếu mảng là {4, 2, 1, 3} thì cần 2 lần hoán đổi

• Hoán đổi arr[0] với arr[2]
• Hoán đổi arr[2] với arr[3]

Thuật toán

1. Tạo vector cặp trong C++ với phần tử đầu là giá trị mảng và phần tử thứ hai là chỉ số mảng.
2. Sắp xếp vector cặp theo phần tử đầu của các cặp.
3. Duyệt vector và kiểm tra nếu chỉ số ánh xạ với giá trị đúng hay không, nếu không thì tiếp tục hoán đổi cho đến khi phần tử đặt đúng vị trí và đếm số lần hoán đổi.

Ví dụ mã 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 << "Số lần hoán đổi tối thiểu = " << getMinSwaps(arr, n) << endl;
    return 0;
}

Khi biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra sau

Đầu ra

Số lần hoán đổi tối thiểu = 2