সি++-এ অ্যারেতে ক্রস লাইন গণনা

বহিরাগত উপাদান বিশিষ্ট একটি অনসর্টেড অ্যারে দেওয়া আছে। লক্ষ্য হল অ্যারে সর্ট হওয়ার পর ক্রস লাইন গণনা করা। ক্রস লাইন নিচের মতো গণনা করা হয়:

Arr[] = { 1,2,4,3,5 } এখানে ৩টি ক্রস লাইন আছে।
Arr[] = { 1,2,3,4,5 } এখানে ক্রস লাইন নেই কারণ অ্যারে ইতিমধ্যে সর্টেড।

ইনসারশন সর্ট ব্যবহার করে ক্রস লাইন গণনা করা হয়। ডানে থেকে একটি উপাদান বাম পাশের সর্টেড অংশে যোগ হয়। প্রতিবার উপাদানটি সঠিক পজিশনে যাওয়ার সময় count বাড়ানো হয় কারণ সেটি তার চেয়ে বড় সব উপাদানকে পার করছে।

উদাহরণ

ইনপুট: arr[] = {4,3,1,2}

আউটপুট: অ্যারেতে ক্রস লাইন সংখ্যা: ৫

ব্যাখ্যা: ৪-৪ এবং ৩-৩ লাইন ১-১ এবং ২-২ কাটে। মোট ৪টি ক্রস লাইন। ৪-৪ এবং ৩-৩ একসাথে একবার কাটে। মোট ৪+১=৫।

ইনপুট: arr[] = { 0,1,5,3 }

আউটপুট: অ্যারেতে ক্রস লাইন সংখ্যা: ১

ব্যাখ্যা: ৫-৫ এবং ৩-৩ একসাথে একবার কাটে। মোট ১টি ক্রস লাইন।

অ্যাপ্রোচ

বহিরাগত সংখ্যার ইন্টিজার অ্যারে arr[] নেওয়া হয়।
insertionSort(int arr[], int n) ফাংশন অ্যারে এবং দৈর্ঘ্য গ্রহণ করে সর্ট করার পর ক্রস লাইন সংখ্যা রিটার্ন করে।
প্রাথমিক ক্রস লাইন ০। count ভেরিয়েবল।
প্রথম উপাদান ইতিমধ্যে সর্টেড, তাই i=1 থেকে i
while (j>=0 && arr[j] > item) লুপে সব বড় উপাদান ডানে শিফ্ট করা হয়। প্রতিটি শিফ্টের জন্য count বাড়ানো হয় (এই সব/item দ্বারা কাটা হয়)।
while লুপ শেষে item সঠিক পজিশনে arr[j+1]-এ রাখা হয়।

উদাহরণ কোড

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

int insertionSort(int arr[], int n) {
    int count = 0;
    int item, j;
    for (int i = 1; i < n; i++) {
        item = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > item) {
            arr[j + 1] = arr[j];
            j = j - 1;
            count++;
        }
        arr[j + 1] = item;
    }
    return count;
}

int main() {
    int arr[] = { 4,5,3,1,2 };
    int n = 5;
    cout << "Number of cross lines: " << insertionSort(arr, n);
    return 0;
}

আউটপুট

Number of cross lines: 8