সি++ কোড: অ্যারে সর্টেড করার জন্য অপারেশন সংখ্যা গণনা করুন

একটি অ্যারে A দেওয়া আছে n উপাদানের সাথে (n বিজোড়)। A প্রথম nটি প্রাকৃতিক সংখ্যার পারমুটেশন। একটি ফাংশন f(i) আছে যা i (০ থেকে 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-এর সাইজ
Ans := 0
loop:
    f := 0
    for j := 0 to n-2:
        if A[j] > A[j+1]: f := 1
    if !f: break
    for j := (Ans & 1); j < n-1; j += 2:
        if A[j] > A[j+1]: swap(A[j], A[j+1])
    Ans++
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 }