আমাদের 1 থেকে n এর মধ্যে সংখ্যার অ্যারে দেওয়া হয়েছে। এখানে লক্ষ্য হল নম্বর খুঁজে বের করা। প্রদত্ত অ্যারে সাজানোর জন্য প্রয়োজনীয় 'moveto front' অপারেশনগুলির। অ্যারের কোনো পুনরাবৃত্তি নেই। 'মুভ টফ্রন্ট' অপারেশন একটি উপাদান বাছাই করে এবং প্রথম অবস্থানে রাখে, এখানে সূচক 0 এ।
আমরা প্রান্ত থেকে অ্যারেটি অতিক্রম করব, যদি উপাদানটি সঠিক অবস্থানে থাকে তবে অন্য কোন সরানোর প্রয়োজন নেই। 1 থেকে n পর্যন্ত উপাদানগুলির জন্য, arr[i] উপাদানের অ্যারেতে সঠিক অবস্থানটি সূচক i+1 কে হারাতে হবে। arr[0] 1 হওয়া উচিত, arr[1] হওয়া উচিত 2 এবং…….arr[n-1] হওয়া উচিত n।
ইনপুট
Arr[]= { 4,3,2,1 } আউটপুট
Minimum move-to-front operations: 3
ব্যাখ্যা
Pull 3, 3,4,2,1 count=1 Pull 2, 2,3,4,1 count=2 Pull 1, 1,2,3,4 count=3
ইনপুট
Arr[]= { 6,1,2,5,4,3 } আউটপুট
Minimum move-to-front operations: 5
ব্যাখ্যা
Pull 5, 5,6,1,2,4,3 count=1 Pull 4, 4,5,6,1,2,3 count=2 Pull 3, ,4,5,6,1,2 count=3 Pull 2, 2,3,4,5,6,1 count=4 Pull 1, 1,2,3,4,5,6 count=5
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
পূর্ণসংখ্যা অ্যারে Arr[] সংখ্যা 1 থেকে n সংরক্ষণ করে।
-
পূর্ণসংখ্যা পরিবর্তনশীল আকার অ্যারের দৈর্ঘ্য সংরক্ষণ করে Arr[>
-
ফাংশন movetoFront(int arr[], int n) ইনপুট হিসাবে একটি অ্যারে এবং এর দৈর্ঘ্য নেয় এবং সেই প্রদত্ত অ্যারে সাজানোর জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক 'মুভ-টু-ফ্রন্ট' অপারেশন প্রদান করে।
-
কাউন্ট ভেরিয়েবল অ্যারের আকারের সাথে আরম্ভ করা হয় কারণ অর্ডার অ্যারে কমার ক্ষেত্রে সমস্ত উপাদান সরানো যেতে পারে।
-
শেষ সূচক থেকে ট্র্যাভার্সিং শুরু করুন এবং সামনের দিকে এগিয়ে যান, যদি উপাদানের মান গণনার সমান হয়, (1 থেকে n-এর মধ্যে বাছাই করা উপাদানগুলির জন্য, n শেষ, n-1 দ্বিতীয় শেষ এবং তাই) তারপর সেই উপাদান হিসাবে গণনা হ্রাস করুন সঠিক অবস্থানে।
-
এইভাবে লুপের শেষে, গণনা পছন্দসই ফলাফল দেয়।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
// Calculate minimum number of moves to arrange array
// in increasing order.
int movetoFront(int arr[], int n){
//take count as all elements are correctly placed
int count = n;
// Traverse array from end
for (int i=n-1; i >= 0; i--){
// If current item is at its correct position,
//decrement the count
//range is 1 to n so every arr[i] should have value i+1
//1 at 0 index, 2 at 1 index........
if (arr[i] == count)
count--;
}
return count;
}
int main(){
int Arr[] = {5, 3, 4, 7, 2, 6, 1};
int size = 7;
cout <<"Minimum 'move-to-front' to sort array:"<< movetoFront(Arr, size);
return 0;
} আউটপুট
Minimum 'move-to-front' to sort array:6
