सी ++ में एक सरणी को सॉर्ट करने के लिए "मूव-टू-फ्रंट" चाल की न्यूनतम संख्या की गणना करें

हमें 1 से n के बीच की संख्याओं की एक सरणी दी गई है। यहां लक्ष्य नहीं खोजना है। दिए गए सरणी को सॉर्ट करने के लिए आवश्यक 'मोवेटो फ्रंट' संचालन। सरणी में कोई दोहराव नहीं है। 'मूव टूफ्रंट' ऑपरेशन एक तत्व को चुनता है और इंडेक्स 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