โค้ด C++ นับรอบการทำงานเพื่อเรียงอาร์เรย์

สมมติว่าเรามีอาร์เรย์ A ขนาด n (n คี่) A เป็นการจัดเรียงของ n จำนวนธรรมชาติแรก มีฟังก์ชัน f(i) รับ i ในช่วง 0 ถึง n-2 ทำ: ถ้า A[i] > A[i+1] สลับค่า ต้องนับจำนวนรอบเพื่อให้ A เรียงลำดับครั้งแรก

เช่น ถ้าอินพุตคือ A = [4, 5, 7, 1, 3, 2, 6] เอาต์พุตจะเป็น 5 สถานะอาร์เรย์หลังแต่ละรอบ: [4,5,1,7,2,3,6], [4,1,5,2,7,3,6], [1,4,2,5,3,7,6], [1,2,4,3,5,6,7], [1,2,3,4,5,6,7]

ขั้นตอนการแก้ปัญหา

n := ขนาดของ A
f := 0
Ans := 0
for Ans := 0;;:
    f := 0
    for j := 0 ถึง n-2:
        if A[j] > A[j+1]: f := 1
    if not f: break
    for j := (Ans AND 1); j < n-1; j += 2:
        if A[j] > A[j+1]: swap A[j], A[j+1]
    เพิ่ม Ans ขึ้น 1
return Ans

ตัวอย่างโค้ด

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

int solve(vector<int> A) {
    int n = A.size();
    bool f = 0;
    int Ans = 0;
    for (Ans = 0;;) {
        f = 0;
        for (int j = 0; j < n - 1; j++)
            if (A[j] > A[j + 1]) f = 1;
        if (!f) 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<int> A = { 4, 5, 7, 1, 3, 2, 6 };
    cout << solve(A) << endl;
}

อินพุต

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