सी ++ में एक सरणी में क्रॉस लाइनों की गणना करना

हमें अलग-अलग तत्वों की एक सरणी दी गई है जो क्रमबद्ध नहीं हैं। लक्ष्य सरणी को क्रमबद्ध करने के बाद क्रॉस लाइनों को खोजना है। क्रॉस लाइन की गणना नीचे दर्शाए अनुसार की जाती है -

• Arr[]={ 1,2,4,3,5 } नीचे दिखाए गए अनुसार 3 क्रॉस लाइन हैं

• एआर [] ={ 1,2,3,4,5}। कोई क्रॉस लाइन नहीं है क्योंकि सरणी पहले से ही क्रमबद्ध है।

हम सम्मिलन सॉर्ट का उपयोग करके क्रॉस लाइनों की गणना करेंगे जिसमें दाईं ओर से एक तत्व को इसके बाईं ओर सॉर्ट किए गए तत्वों में जोड़ा जाता है। हर बार जब तत्व को सॉर्ट किए गए भाग में जोड़ा जाता है, तो वृद्धि की गणना की जाती है क्योंकि यह अपनी सही स्थिति में जाता है। यह उन सभी तत्वों को पार करके गुजरेगा जो बड़े हैं।

आइए उदाहरणों से समझते हैं।

इनपुट - गिरफ्तारी [] ={4,3,1,2 }

आउटपुट - सरणी में क्रॉस लाइनों की संख्या - 5

स्पष्टीकरण - रेखा 4-4 और 3-3 रेखा 1-1 और 2-2 को पार करती है। कुल 4 क्रॉस लाइन।

4-4 और 3-3 दोनों एक दूसरे को एक बार पार करते हैं। कुल 4+1=5 क्रॉस लाइन।

इनपुट - गिरफ्तारी [] ={ 0,1,5,3 }

आउटपुट - सरणी में क्रॉस लाइनों की संख्या - 1

स्पष्टीकरण - 5-5 और 3-3 दोनों एक दूसरे को एक बार पार करते हैं। कुल 1 क्रॉस लाइन।

नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है

• हम एक पूर्णांक सरणी लेते हैं arr[] अलग-अलग संख्याओं के साथ आरंभ किया गया।

• फ़ंक्शन सम्मिलन सॉर्ट (int arr [], int n) इनपुट के रूप में एक सरणी और उसकी लंबाई लेता है और सॉर्ट करने के बाद परिणाम के रूप में क्रॉस लाइनों की गिनती देता है।

• क्रॉस लाइनों की प्रारंभिक संख्या को 0 के रूप में लें। गणना चर का उपयोग किया जाता है।

• पहला तत्व पहले से ही क्रमबद्ध है, इसलिए दूसरे तत्व से शुरू होकर अंत तक (i=1 से i

• अब सभी तत्वों को सही शिफ्ट करें यदि वे> आइटम और j>0 हैं। प्रत्येक पारी वेतन वृद्धि की गणना के रूप में इन सभी को आइटम द्वारा पार किया जाता है।

• लूप के अंत में आइटम को उसकी सही स्थिति में रखें जो कि 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