আমাদের আলাদা আলাদা উপাদানের একটি অ্যারে দেওয়া হয়েছে যা সাজানো হয়নি৷ লক্ষ্য হল অ্যারে সাজানোর পর ক্রস লাইন খুঁজে বের করা। ক্রস লাইনগুলি নীচে দেখানো হিসাবে গণনা করা হয় -
-
Arr[]={ 1,2,4,3,5 } নীচে দেখানো হিসাবে 3টি ক্রস লাইন আছে
-
Arr[]={ 1,2,3,4,5 }। কোনো ক্রস লাইন নেই কারণ অ্যারেটি ইতিমধ্যেই সাজানো হয়েছে৷
৷
আমরা সন্নিবেশ বাছাই ব্যবহার করে ক্রস লাইন গণনা করব যেখানে ডান দিক থেকে একটি উপাদান তার বাম দিকে সাজানো উপাদানগুলিতে যোগ করা হয়েছে। প্রতিবার সাজানো অংশে উপাদান যোগ করা হলে, এটি সঠিক অবস্থানে যাওয়ার সাথে সাথে বৃদ্ধির সংখ্যা। এটি বৃহত্তর সমস্ত উপাদান অতিক্রম করে যাবে৷
উদাহরণ দিয়ে বোঝা যাক।
ইনপুট − arr[]={4,3,1,2 }
আউটপুট − অ্যারেতে ক্রস লাইনের সংখ্যা − 5
ব্যাখ্যা − লাইন 4-4 এবং 3-3 লাইন 1-1 এবং 2-2 অতিক্রম করে। মোট 4টি ক্রস লাইন।
4-4 এবং 3-3 উভয়ই একে অপরকে একবার অতিক্রম করে। মোট 4+1=5 ক্রস লাইন।
ইনপুট − arr[]={ 0,1,5,3 }
আউটপুট − অ্যারেতে ক্রস লাইনের সংখ্যা − 1
ব্যাখ্যা − 5-5 এবং 3-3 উভয়ই একে অপরকে একবার অতিক্রম করে। মোট 1 ক্রস লাইন।
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
আমরা একটি পূর্ণসংখ্যা অ্যারে অ্যারে নিই [] স্বতন্ত্র সংখ্যার সাথে শুরু।
-
ফাংশন সন্নিবেশSort(int arr[], int n) ইনপুট হিসাবে একটি অ্যারে এবং এর দৈর্ঘ্য নেয় এবং বাছাই করার পরে এটি ফলাফল হিসাবে ক্রস লাইনের গণনা প্রদান করে।
-
ক্রস লাইনের প্রারম্ভিক সংখ্যা 0 হিসাবে নিন। কাউন্ট ভেরিয়েবল ব্যবহার করা হয়।
-
প্রথম উপাদানটি ইতিমধ্যেই সাজানো হয়েছে, তাই দ্বিতীয় উপাদান থেকে শুরু করে শেষ পর্যন্ত (i=1 থেকে i
-
এখন সমস্ত উপাদান ডানদিকে স্থানান্তর করুন যদি সেগুলি> আইটেম এবং j>0 হয়। প্রতিটি শিফট ইনক্রিমেন্টের জন্য এই সমস্ত আইটেম দ্বারা অতিক্রম করা হয় হিসাবে গণনা.
-
while লুপের শেষে আইটেমটিকে তার সঠিক অবস্থানে রাখুন যা হল arr[j+1]।
-
সমস্ত উপাদানের জন্য এটি করুন এবং তারা অতিক্রমকারী উপাদানগুলিকে গণনা করুন৷
-
সংখ্যা হিসাবে গণনার বৃদ্ধির মান। ক্রস লাইনের সম্ভব।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int insertionSort(int arr[], int n){
int count=0;
int item;
int j;
for (int i = 1; i < n; i++){
item = arr[i];
j = i - 1;
//insert element at correct position in sorted part, no. of elements it passes
//from right till correct position is count of cross lines.
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
