Đếm số lần lặp để sắp xếp mảng hoán vị bằng phép đổi chỗ lân cận theo quy tắc bằng C++

Mô tả bài toán

Mảng A n phần tử (n lẻ) là hoán vị 1..n. Hàm f(i): nếu A[i]>A[i+1] thì đổi chỗ. Mỗi vòng lặp áp dụng f cho các chỉ số chẵn hoặc lẻ xen kẽ (vòng 0: chỉ số chẵn, vòng 1: chỉ số lẻ,...). Đếm số vòng đến khi mảng sắp xếp tăng dần.

Ví dụ

A=[4,5,7,1,3,2,6] → 5 vòng.

Thuật toán

Mô phỏng: mỗi vòng kiểm tra nếu mảng đã sắp xếp thì dừng. Ngược lại áp dụng đổi chỗ cho các cặp (i,i+1) với i có parity = vòng % 2. Đếm vòng.

Code C++

#include <bits/stdc++.h>
using namespace std;

int solve(vector A) {
    int n = A.size();
    int ans = 0;
    while (true) {
        bool sorted = true;
        for (int j = 0; j < n-1; j++)
            if (A[j] > A[j+1]) { sorted = false; break; }
        if (sorted) break;
        for (int j = (ans & 1); j < n-1; j += 2)
            if (A[j] > A[j+1]) swap(A[j], A[j+1]);
        ans++;
    }
    return ans;
}

int main() {
    vector A = {4,5,7,1,3,2,6};
    cout << solve(A) << endl;
    return 0;
}

Đầu vào / Đầu ra

Input: {4,5,7,1,3,2,6}

Output: 5